题目描述

有 $n$ 个城市，$m$ 条有向道路，第 $i$ 条道路从 $u_i$ 到 $v_i$，长度为 $w_i$（$w_i > 0$）。

快递员要从 1 号城市出发，把包裹送到 $n$ 号城市。途中必须在至少一个「加油站」城市加油，否则无法完成配送。

给出 $k$ 个加油站城市编号，求完成配送的最短总路程；如果无法完成，输出 $-1$。

注意：起点或终点本身是加油站也算「途中经过」。

输入格式

第一行三个整数 $n, m, k$（$1 \le n \le 10^5$，$1 \le m \le 2 \times 10^5$，$1 \le k \le n$）。

第二行 $k$ 个整数，表示加油站城市编号（互不相同）。

接下来 $m$ 行，每行三个整数 $u_i, v_i, w_i$（$1 \le w_i \le 10^9$）。

输出格式

一个整数，表示最短总路程；无法完成输出 $-1$。

样例 #1

5 6 1
3
1 2 2
2 3 3
3 5 1
1 4 10
4 5 1
2 4 1

6

路线 $1 \to 2 \to 3 \to 5$，长度 $2+3+1=6$，经过加油站 3。

提示

对于 40% 的数据，$n \le 1000$，$m \le 5000$；对于 100% 的数据，$n \le 10^5$，$m \le 2 \times 10^5$。