#25 「 着火了 」

统计

森林着火了,火势还在不断蔓延。

R君作为森林管理员,看到火势失去控制、在森林中四处蔓延,心里很慌。

经过R君平日仔细的研究,这个森林的火势传播可以看成一个n个节点的带边权的无向图(节点标号为1-n),每个节点代表森林的一个区域,一条边(u,v,w)代表着火势从区域u传播到区域v需要花费w的时间。并且整个森林是一个连通图,一旦着火,没有节点可以幸免。

通过自动化的IoT设备,R君观察到了0时刻有k处起火点,然后大火就按照火势传播图的规则蔓延开来。

不幸的是森林里有q个区域存在着居民,所以R君非常想知道火势蔓延到这q个区域的时间从而展开营救行动。

然而R君觉得这个问题太难了,于是找到了学OI的你。

输入格式

第一行四个整数n, m, k, q,表示图的点数、边数、起火点数量、存在居民的区域数量。

接下来m行,每行三个正整数u, v, w,表示一条u到v,边权为w的无向边。

接下来一行k个正整数,表示0时刻k个起火点的节点编号。

接下来一行q个正整数,表示询问的q个居民区的节点编号。

输出格式

输出q行,每行一个整数,表示火势蔓延到该点的时间。

样例数据

input

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

output

0
5
2
0
4

数据规模与约定

$1 \le n,m \le 10000$, $1 \le k,q,u,v \le n$, $1 \le w \le 10000$。

时间限制:1s

空间限制:512MB

Author: zrt