解题思路

• 核心思路

普通的最短路状态如果直接记录“当前所在房间 + 当前钥匙颜色”，状态会非常大。关键观察是：

对于同一种颜色 $c$ 的传送门，它们会把若干房间划分成若干个连通块。

如果当前在房间 $u$，并且购买了颜色 $c$ 的钥匙，那么 hy 可以在颜色 $c$ 所在的同色连通块中任意移动，之后到达这个连通块内的任意房间，且不再产生额外费用。

题目内容

“光之女皇”是泰拉瑞亚困难模式的神圣之地Boss，对战可选，但并非游戏主线所需。尽管初期可通过召唤物“七彩草岭”通常认为应在击败石巨人后再发起挑战。hy想挑战光之女皇，却被邪恶的zzh和lyf将”七彩草蛉“藏入迷宫以阻挠。

迷宫由 $n$ 个房间与 $q$ 条传送门构成，第 $i$ 条传送门双向连接房间 $x_i$ 与房间 $y_i$，颜色为 $c_i$ ; 打开颜色 $c_i$ 的传送门需支付费用 $c_i$ 购买对应钥匙，每次仅能携带一把钥匙(钥匙可无限次使用、使用后不消失)，也可购买新钥匙替换旧钥匙。

仅当持有某颜色的钥匙时，才能使用该颜色的传送门，你可以在任何房间随时支付费用 $c_i$ 购买一把颜色为 $c_i$ 的新钥匙，并替换掉当前持有的钥匙。

zzh 和 lyf 在房间中一共放置了 $k$ 只“七彩草蛉”，作为幸运房间——如果某个房间有“七彩草蛉”，可立即免费(费用 $0$ )制作一把任意颜色钥匙；但在其他房间制作钥匙仍需支付相应颜色费用。

hy 从房间 $1$ 出发，目标是到达(或起始于)至少一个草蛉房间以获得幸运并最终抵达房间 $n$ ；若无法完成任务，则失败。请计算 hy 完成任务的最小总花费；若无法完成，则直接输出 $-1$ 。

【名词解释】

连通块：同一颜色传送门在迷宫中形成的可互达房间集合。

输入描述

第一行输入三个整数 $n,k,q(1≤n,q≤2×10^5;1≤k≤n)$ 分别表示房间数，草蛉数量和传送数量。

第二行输入 $k$ 个整数 $p_1,p_2,...,p_k(1≤p_i≤n)$ 表示第 $i$ 只草岭所在的房间编号，可能有多只草岭位于同个房间。

此后 $q$ 行，第 $i$ 行输入三个整数 $x_i,y_i,c_i(1≤x_i,y_i≤n;1≤c_i≤2×10^5)$ 表示第 $i$ 条传送门双向连接房间 $x_i$ 出与房间 $y_i$ ，颜色为 $c_i$ 。

输出描述

输出一个整数，表示完成任务的最小总花费；若无法完成，则输出 $-1$ 。

样例1

输入

3 1 3
2
1 2 1
2 3 1
3 1 2

输出

说明

样例2

输入

输出

说明

在这个样例中，花费 $1$ 购买颜色 $1$ 的钥匙，依次穿越 $1->3->2->5->6$。因为 $6$ 号房间有“七彩草蛉”，免费制作颜色 $5$ 的钥匙；随后，依次穿越 $6->7->8$ 。最终，总花费 $1$ 。

样例3

输入

8 1 11
2
1 3 1
1 4 2
2 3 1
2 5 1
3 4 3
3 6 3
3 7 3
4 8 4
5 6 1
6 7 5
7 8 5

输出

6

说明

在这个样例中，依次穿越 $1->3->2->5->6->7->8$，总花费 $1+5=6$ 。