题目描述

114514 年，人类的科技已经十分发达，星际旅行已变得十分容易。人类已经涉足的星球有地球（编号为 $1$）和其他 $n-1$ 颗星球（编号分别为 $2,3,\ldots ,n$），并在这些星球之间建立了 $m$ 条双向航线，支付一定的费用就可以乘坐航班通过这些路线。

目前市面上流通着两种货币：原石和摩拉。在编号为 $i$ 的星球，你可以用 $1$ 个原石兑换 $a_i$ 个摩拉（可以无限次兑换，因为原石比较珍贵，所以只能用原石兑换摩拉而不能用摩拉兑换原石）。星球之间的航行既可以用原石支付，也能用摩拉支付，具体来说，通过第 $j$ 条航线时，你可以用 $c_j$ 个原石或 $d_j$ 个摩拉支付。通过一条航线时只能选择一种支付方式，不能同时使用原石和摩拉支付，但对于不同航线，可使用不同的支付方式。

但可惜的是，现在所有星球都被卷入了大坍缩之中，在坍缩结束后，他们发现原来的路线没有改变，但是所有的摩拉都消失了，只剩下了原石。因此所有的路线只能依靠原石支付。

现在为了恢复星际的正常运输，因此星际快递公司从自由状态不得不转入战备状态。第一批重建计划涉及的是 $k$ 个星球，因为星际快递公司的原石也十分稀少，因此他们也需要选择一条花费最少的路线作为重建的开始来进行资源补充。因此他们想知道从 $k$ 个星球中选择一个起点和一个终点(显然起点和终点不能是同一个点)，这样的线路的最小花费是多少？

输入

第一行包含一个整数 $T\ (1$\le$T$\le$10)$，代表测试用例的数量。

对于每个测试用例，第一行包含两个整数 $n,m\ (1$\le$n,m$\le$100000)$，代表星球的数量和航道的数量。

接下来m行每行包含三个整数 $x_i,y_i,c_i\ (1$\le$x_i,y_i$\le$n,1$\le$c_i$\le$100000)$。表示一条连接 $x_i,y_i$ ,花费为 $c_i$ 原石的无向边。

然后一行包含一个整数 $k\ (1$\le$k$\le$n)$，即第一批重建计划涉及的星球数。

然后一行包含 $k$ 个互不相同的整数 $a_i\ (1$\le$a_i$\le$n)$，代表选定的不同的星球。

输入保证图连通。

输出

每行一个整数，代表对应测试用例的答案。

1
5 6
1 2 1
2 3 3
3 1 3
2 5 1
2 4 2
4 3 1
3
1 3 5

2

见附件中的sample.in

见附件中的sample.out

样例说明

该样例中若选择 $1$ 号星球为起点， $5$ 号星球为终点，那么花费最短，为 $2$

数据范围

每组数据点10分，共10个数据点

附件下载

T2sample