题目描述

给定一个包含 $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$ 之前执行 移动 操作的最小次数。

样例输入 1

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

样例输出 1

5

高桥可以按照以下方式到达顶点 $N$。

• 从顶点 $1$ 移动到顶点 $2$。
• 从顶点 $2$ 移动到顶点 $3$。
• 触发顶点 $3$ 上的开关。这会翻转图中所有边的可通过性。
• 从顶点 $3$ 移动到顶点 $1$。
• 从顶点 $1$ 移动到顶点 $4$。
• 触发顶点 $4$ 上的开关。这会再次翻转图中所有边的可通过性。
• 从顶点 $4$ 移动到顶点 $5$。

在这里，总共执行了五次移动操作，这是最小可能次数。

样例输入 2

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

样例输出 2

-1

所给出的图可能是不连通的或包含多条边。在这个样例输入中，高桥无法到达顶点 $N$，因此应该输出 $-1$。