A. 出勤规划
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

橘猫发现了一个地图，这个地图上面居然有 maimai 的分布图！塑料一听就忍不住了，于是他把地图要了过来研究。

这张地图由 $$$n$$$ 个点和 $$$m$$$ 条带权无向边组成，现在我们定义 $$$f(u,v)$$$ 为点 $$$u$$$ 到点 $$$v$$$ 的最短距离。

塑料只关心其中的 $$$k$$$ 个点 $$$\{a_1,a_2,...,a_k\}$$$，于是他把这 $$$k$$$ 个点提取出来并记录下它们之间的距离，而这 $$$k$$$ 个点组成了一个新的无向图，边 $$$(i,j)$$$ 的权值为原图中的 $$$f(a_i,a_j)$$$。

就当塑料还在规划路线的时候，橘猫突然对这个新的无向图的最小生成树的所有边的权值之和很感兴趣，于是他把这个问题留给了塑料，但显然笨笨的塑料并不擅长解决这种问题，于是这个问题就交给你啦！

Input

本题有多组测试数据。

第一行输入一个数字 $$$T$$$ ($$$1 \leq T \leq 2 \times 10^4$$$)，表示有 $$$T$$$ 组数据；

接下来对于每组数据，第一行输入三个整数 $$$n,m,k$$$ ($$$1 \leq n \leq 5 \times 10^5$$$, $$$n-1 \leq m \leq 5 \times 10^5$$$, $$$1 \leq k \leq n$$$)，表示点的数量和边的数量；

接下来 $$$m$$$ 行，每行三个数字 $$$x,y,w$$$ ($$$1 \leq x,y \leq n$$$, $$$1 \leq w \leq 10^8$$$)，表示点 $$$x$$$ 到点 $$$y$$$ 有一条长度为 $$$w$$$ 的路径。

接下来一行 $$$k$$$ 个数字 $$$\{a_1,a_2,...,a_k\}$$$，表示塑料关心的这 $$$k$$$ 个点。

保证所有测试样例的 $$$n,m$$$ 之和均不超过 $$$5 \times 10^5$$$。

保证给出的图是连通的。

Output

对于每组测试样例，输出一个数字 $$$x$$$，表示这个最小生成树的边的权值之和。

Example
Input
2
5 4 3
1 2 3
1 3 5
1 4 7
2 5 6
3 4 5
3 6 3
1 2 4
1 3 5
2 3 2
3 2 7
1 1 4
2 2 6
1 2 3
Output
26
6
Note

第一组测试样例的原图和新图如下：

原图新图

可以发现：

  • $$$f(1,2) = 3, f(1,3) = 5, f(1,4) = 7, f(1,5) = 9$$$
  • $$$f(2,3) = 8, f(2,4) = 10, f(2,5) = 6$$$
  • $$$f(3,4) = 12, f(3,5) = 14$$$
  • $$$f(4,5) = 16$$$

其中，塑料只关心 $$$3,4,5$$$ 这三个点，可以发现最后的生成树只包含 $$$(3,4),(3,5)$$$ 这两条边，故生成树的权值为 $$$12+14=26$$$。

对于第二组测试样例：请注意可能有重边和自环。