治安点

时间限制: 300 ms 内存限制: 65536 kb
总通过人数: 0 总提交人数: 0

题目

知识点:最短路,最短路的优化

贝克兰德有n个城镇,这些城镇之间有m条道路连接,每条道路有一个长度l。

zf在其中k个城镇设置了治安点。当一个城镇发生事件时,任意一个治安点都可以派人前往。但是为了节省资源,往往会选择距离最近的治安点。

那么请问,对于每一个城镇,最近的治安点距离为多少。

输入

第一行一个整数t表示数据组数($1\le t \le 10$)

每组数据第一行三个正整数n,m,k ($1\le n\le 10^3,n-1\le m\le n*n/2,1\le k\le n$)

第二行k个整数表示治安点所在的位置。

接下来m行,每行三个整数x,y,z,表示x,y之间有一条权值为z的边(无向边) ($1\le x,y\le n,1\le z \le 10000$)

输出

每组数据一行,n个数

输入样例

1
4 7 2 
1 4
1 2 7
1 3 2
1 4 6 
2 1 1
2 4 1
3 2 1
3 4 3

输出样例

0 1 2 0

相关推荐