题目内容

“光之女皇”是泰拉瑞亚困难模式的神圣之地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$ 。