Source : 2019贵州省选Day2
Description

  J 国有 nn 座城市,这些城市之间通过 mm 条单向道路相连,已知每条道路的长度。
  一次,居住在 J 国的 Rainbow 邀请 Vani 来作客。不过,作为一名资深的旅 行者,Vani 只对 J 国的 kk 座历史悠久、自然风景独特的城市感兴趣。
  为了提升旅行的体验,Vani 想要知道他感兴趣的城市之间“两两最短路”的 最小值(即在他感兴趣的城市中,最近的一对的最短距离)。
  也许下面的剧情你已经猜到了——Vani 这几天还要忙着去其他地方游山玩水,就请你帮他解决这个问题吧。

Input

  每个测试点包含多组数据,第一行是一个整数 TT,表示数据组数。注意各组数据之间是互相独立的。
  对于每组数据,第一行包含三个正整数 n,m,kn,m,k,表示 J 国的 nn 座城市(从 1 n1~n 编号),mm 条道路,Vani 感兴趣的城市的个数 kk
  接下来 mm 行,每行包括 33 个正整数 x,y,zx,y,z,表示从第 xx 号城市到第 yy 号城市有一条长度为 zz 的单向道路。注意 xx, yy 可能相等,一对 xx,yy 也可能重复出现。
  接下来一行包括 kk 个正整数,表示 Vani 感兴趣的城市的编号。

Output

  输出文件应包含 TT 行,对于每组数据,输出一个整数表示 kk 座城市之间两两最短路的最小值。

Sample Input
2
6 7 3
1 5 3
2 3 5
1 4 3
5 3 2
4 6 5
4 3 7
5 6 4
1 3 6
7 7 4
5 3 10
6 2 7
1 2 6
5 4 2
4 3 4
1 7 3
7 2 4
1 2 5 3
 
Sample Output
5
6
Hint

样例说明
  对于第一组数据,1 到 3 最短路为 5;1 到 6 最短路为 7;3,6 无法到达,所以最近的两点为 1,3,最近的距离为 5。
  对于第二组数据,1 到 2 最短路为 6;5 到 3 最短路为 6;其余的点均无法互相达,所以最近的两点为 1,2 和 5,3,最近的距离为 6。
数据规模与约定
enter image description here