Exber 有一个无向图,其中有 $$$n$$$ 个顶点和 $$$m$$$ 个边。第 $$$i$$$ 条边连接顶点 $$$u_i$$$ 和 $$$v_i$$$ 并具有权重 $$$w_i$$$。
对于每条路径,让其中边的权重组成一个集合$$$S$$$;那么该路径的长度定义为$$$\operatorname{mex}(S)$$$。这里,$$$\operatorname{mex}(S)$$$表示集合$$$S$$$的最小排除(MEX)$$$^{\text{*}}$$$。 设$$$\mathrm{dis}(u,v)$$$表示从$$$u$$$开始到$$$v$$$结束的所有路径中的最小路径长度。
现在,Exber 想要构造一个具有 $$$q$$$ 个顶点的新图。在新图中,第 $$$i$$$ 个顶点的颜色为 $$$c_i$$$。最初,该图中没有边。如果 Exber 添加一条连接顶点 $$$u$$$ 和顶点 $$$v$$$ 的边,则会花费 $$$\mathrm{dis}(c_u,c_v)$$$ 时间。如果给定图中顶点 $$$c_u$$$ 和顶点 $$$c_v$$$ 没有连接,Exber 无法在新图中添加连接顶点 $$$u$$$ 和顶点 $$$v$$$ 的边。
确定 Exber 连接新图所需花费的最短时间。
$$$^{\text{*}}$$$整数集合 $$$S_1, S_2, \ldots, S_k$$$ 的最小排除 (MEX) 被定义为集合 $$$S$$$ 中不出现的最小非负整数 $$$x$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$q$$$ ($$$1\le n,m\le 3\cdot 10^5$$$, $$$1\le q\le n$$$) — 分别是图中的节点数、图中的边数和新图中的节点数。
接下来的 $$$m$$$ 行每行包含三个整数 $$$u$$$、$$$v$$$ 和 $$$w$$$ ($$$1\le u,v\le n$$$, $$$0\le w\le m$$$),表示顶点 $$$u$$$ 和$$$v$$$。
下一行包含$$$q$$$整数$$$c_i$$$ ($$$1\le c_i\le n$$$),表示新图中顶点$$$i$$$的颜色为$$$c_i$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$3\cdot 10^5$$$。
保证所有测试用例的 $$$m$$$ 总和不超过 $$$3\cdot 10^5$$$。
保证所有测试用例的 $$$q$$$ 总和不超过 $$$3\cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数 - Exber 连接新图所需花费的最短时间。如果不可能,则输出$$$-1$$$。
示例
输入复制
45 6 31 2 02 3 13 4 23 5 15 1 04 5 11 2 410 12 57 2 35 8 08 9 21 8 13 5 010 6 07 4 31 10 03 1 01 7 22 9 06 8 03 5 9 10 610 12 58 2 010 1 16 10 04 2 34 3 23 8 310 7 04 5 16 4 02 10 01 3 07 9 06 1 7 9 55 4 25 1 05 2 01 2 13 4 21 3
输出复制
145-1
注意
在第一个测试用例中,原始图有 $$$5$$$ 个顶点和 $$$5$$$ 个边。新图中顶点的颜色为 $$$1$$$、$$$2$$$ 和 $$$4$$$。
第一个测试用例的原始图。括号内的数字表示新图中顶点的索引,其颜色是该顶点在原图中的索引。 在新图中,Exber 将添加边 $$$(1,2)$$$ 和 $$$(2,3)$$$,第一个边将花费他 $$$1$$$ 时间,第二个边将花费他 $$$0$$$ 时间;因此,总时间为 $$$1$$$。
在第二个测试用例中,原始图有 $$$10$$$ 个顶点和 $$$12$$$ 个边。新图中顶点的颜色为 $$$3$$$、$$$5$$$、$$$9$$$、$$$10$$$ 和 $$$6$$$。
第二个测试用例的原始图。括号内的数字表示新图中顶点的索引,其颜色是该顶点在原图中的索引。 在新图中,Exber 将添加边 $$$(1,2)$$$、$$$(2,3)$$$、$$$(3,4)$$$ 和 $$$(4,5)$$$,每条边将花费他 $$$1$$$ 时间;因此,总时间为 $$$4$$$。