配点 : $500$ 点

問題文

$N$ 個の頂点と $M$ 本の辺からなる無向グラフが与えられます。 $i = 1, 2, \ldots, M$ について、$i$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ を結ぶ無向辺であり、 $a_i = 1$ ならばはじめは通行可能、$a_i = 0$ ならばはじめは通行不能です。 また、頂点 $s_1$ 、頂点 $s_2$ 、$\ldots$ 、頂点 $s_K$ の $K$ 個の頂点にはスイッチがあります。

高橋君は、はじめ頂点 $1$ におり、「下記の移動とスイッチを押すの $2$ つの行動のどちらかを行うこと」を好きなだけ繰り返します。

• 移動 : いまいる頂点と通行可能な辺を介して隣接する頂点を $1$ つ選び、その頂点に移動する。
• スイッチを押す : いまいる頂点にスイッチがあるならば、そのスイッチを押す。その結果、グラフ上のすべての辺の通行可能・通行不能の状態が反転する。すなわち、通行可能である辺は通行不能に、通行不能である辺は通行可能に変化する。

高橋君が頂点 $N$ に到達することが可能かどうかを判定し、可能な場合は頂点 $N$ に到達するまでに行う移動の回数としてあり得る最小値を出力してください。

制約

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 2 \times 10^5$
• $0 \leq K \leq N$
• $1 \leq u_i, v_i \leq N$
• $u_i \neq v_i$
• $a_i \in \lbrace 0, 1\rbrace$
• $1 \leq s_1 \lt s_2 \lt \cdots \lt s_K \leq N$
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $K$

$u_1$ $v_1$ $a_1$

$u_2$ $v_2$ $a_2$

$\vdots$

$u_M$ $v_M$ $a_M$

$s_1$ $s_2$ $\ldots$ $s_K$

出力

高橋君が頂点 $N$ に到達することが不可能な場合は $-1$ を、 可能な場合は頂点 $N$ に到達するまでに行う移動の回数としてあり得る最小値を出力せよ。

5 5 2
1 3 0
2 3 1
5 4 1
2 1 1
1 4 0
3 4

5

高橋君は、下記の手順で行動することで頂点 $N$ に到達できます。

• 頂点 $1$ から頂点 $2$ に移動する。
• 頂点 $2$ から頂点 $3$ に移動する。
• 頂点 $3$ にあるスイッチを押す。これによって、グラフ上のすべての辺の通行可能・通行不能の状態が反転する。
• 頂点 $3$ から頂点 $1$ に移動する。
• 頂点 $1$ から頂点 $4$ に移動する。
• 頂点 $4$ にあるスイッチを押す。これによって、グラフ上のすべての辺の通行可能・通行不能の状態が再び反転する。
• 頂点 $4$ から頂点 $5$ に移動する。

この手順における移動の回数は $5$ 回であり、これが考えられる最小の回数です。

4 4 2
4 3 0
1 2 1
1 2 0
2 1 1
2 4

-1

与えられるグラフは、連結でないことや、多重辺を含むことがあります。 この入力例では、高橋君はどのように行動しても頂点 $N$ に到達することはできないので、$-1$ を出力します。