Migrated from Lutece 2585 小电的女朋友

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

大一学生小电想要和他的女朋友一起上自习，但是小电和他的女朋友不是同一专业的，所以上课地点并不相同，于是下课后小电要到他女朋友的教室去。

品学楼的 $n$ 间教室由 $m$ 条走廊（无向道路）相互连接，但是粗心的小电忘了他和他女朋友上课的具体教室，只知道属于 $k$ 间教室中的不同两间。小电想知道他可能最少要走的距离是多少。作为你电的学生，小电请你帮忙解决他的疑问。

即，给你一个 $n$ 个点 $m$ 条边的无向图，求给定的 $k$ 个点中任意两点距离的最小值，保证图连通。

Input

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

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

接下来m行每行包含三个整数 $x_i,y_i,w_i\ (1\le x_i,y_i\le n,1\le w_i\le 100000)$。表示一条权值为 $w_i$ 的无向边。

然后一行包含一个整数 $k\ (1\le k\le n)$，即节点数。

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

Output

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

Samples

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

Resources

2021 UESTC ICPC Training for Graph