406589: GYM102448 H Hellcife is on fire

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

H. Hellcife is on firetime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

The kingdom of Hellcife has several cities that are connected by some roads. One day, the king of Hellcife, Bair Jolsonaro, decided to set fire on some of these cities, just for fun. It's known that the $$$i$$$-th city has a number $$$T_i$$$, indicating that if the fire reaches that city at time $$$X$$$, then at time $$$X + T_i$$$ this city will be completely burnt. After a city is completely burnt, the fire begins to spread across all the roads that are connected to this city, with speed of one meter per second.

Your task is simple: you have to find, for each city, the amount of time it takes for the city to be completely burnt, knowing that at time 0 the king Bair Jolsonaro set fire on some cities.

Input

The first line of input contains three numbers $$$N$$$, $$$M$$$ and $$$K$$$ ($$$1 \leq N,M,K \leq 10^{5}$$$), indicating the number of cities in Hellcife, the number of roads in Hellcife, and the number of cities Bair Jolsonaro initially set fire, respectively.

Each of the following $$$M$$$ lines contains three integers $$$A_i$$$, $$$B_i$$$, and $$$C_i$$$ ($$$1 \leq A_i,B_i \leq N$$$, $$$A_i \neq B_i$$$, $$$1 \leq C_i \leq 10^{5}$$$), indicating that there is a road between cities $$$A_i$$$ and $$$B_i$$$ with length of $$$C_i$$$ meters.

The next line of input contains $$$N$$$ numbers $$$T_i$$$ ($$$1 \leq i \leq N$$$, $$$1 \leq T_i \leq 10^{5}$$$).

The last line of the input contains $$$K$$$ numbers $$$X_i$$$ ($$$1 \leq i \leq K$$$, $$$1 \leq X_i \leq N$$$), indicating that the $$$X_i$$$-th city was chosen by Bair Jolsonaro to be set on fire in the beginning.

Output

The output consists of $$$N$$$ lines, the $$$i$$$-th of them indicates the amount of time it takes for the $$$i$$$-th city to be completely burnt.

ExamplesInput
5 5 1
1 2 1
2 3 4
3 4 5
4 5 10
1 5 13
1 2 3 4 5
1
Output
1
4
11
20
19
Input
5 18 1
1 3 14877
2 1 81271
1 2 50743
5 1 46485
2 5 41563
5 4 72606
1 2 88401
5 3 56633
2 1 25722
3 1 78857
2 3 95527
5 4 66046
1 4 87400
4 2 49102
3 2 3043
5 3 32836
3 2 13703
4 1 86008
31551 94560 84171 16742 55756
2
Output
151833
94560
181774
160404
191879
Input
7 12 2
6 3 61451
3 5 48225
3 6 18732
5 3 86896
1 5 73979
4 3 49294
3 1 2794
1 5 3449
7 2 86351
4 6 59862
2 1 38972
3 7 20293
36685 6614 81280 91835 68491 81662 10505
2 1
Output
36685
6614
120759
261888
108625
221153
103470
Note

It is guaranteed that from any city you can reach any other city using some roads.

加入题单

上一题 下一题 算法标签: