E - 晶体开关

得分：500分

问题描述

给定一个由$N$个顶点和$M$条边组成的无向图。
对于$i=1,2,\ldots,M$，第$i$条边是一条连接顶点$u_i$和$v_i$的无向边，如果$a_i=1$则初始时是可通过的，如果$a_i=0$则初始时是不可通过的。 此外，图中的$K$个顶点上有开关：顶点$s_1$、顶点$s_2$，$\ldots$，顶点$s_K$。

高橋最初在顶点$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$。

在这个过程中，共进行了五次移动，这也是最少的次数。

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

-1

给定的图可能是非连通的，或者包含多条边。 在这个样例输入中，高橋无论如何都无法到达顶点$N$，因此应该输出$-1$。