1109: 小鱼吃虾米

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:73 Solved:21

Description

”大鱼吃小鱼,小鱼吃虾米。“

但是,小鱼也有变成大鱼的梦想!

小鱼住在一个有 $n$ 个区域的海底世界,区域编号从 $1$ 到 $n$,海底世界中有 $m$ 条**单向通道**,每条通道连接了其中两个区域。

区域 $1$ 有海底世界中唯一的虾米群。

区域 $2$ 到 $n$ 中,有 $k$ 个区域可以作为出生点,即小鱼可以任意选择其中一个区域作为起点,它将从该起点出发,游到区域 $1$,从而吃到虾米群,变成大鱼。

现在小鱼希望选择某个出生点,使得它从该出生点出发,到吃到虾米群的总距离最短。请你帮帮它。

Input

第一行,一个整数 $t$,表示测试案例的个数。($1 \le t \le 10$)

对于每个测试案例:

第一行,三个整数 $n,m,k$,表示海底世界的区域个数、单向通道条数、出生点个数。($2 \le n \le 10^4$,$1 \le m \le 10^4$,$1 \le k \le n - 1$)

第二行,$k$ 个整数,表示出生点的编号 $v_i$。($2 \le v_i \le n$)

接下来 $m$ 行,每行三个整数 $a,b,c$,表示存在一条从区域 $a$ 到区域 $b$ 的长度为 $c$ 的单向通道。($1 \le a,b \le n$,$1 \le c \le 10^5$)

Output

共 $t$ 行,每行一个整数,表示吃到虾米的最短距离,若无论取哪个出生点,都无法吃到虾米,则为 $-1$。

Sample Input Copy

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

Sample Output Copy

3
-1

HINT

样例 $1$:

选择出生点为区域 $3$,则最短距离的路径为 $3 \rarr 4 \rarr 1$,距离为 $2 + 1 = 3$。

样例 $2$:

仅有唯一的出生点区域 $3$,而从区域 $3$ 无法到达区域 $1$,因此输出 $-1$。