F - Virus 2 Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 550 点

問題文

部屋 1, 部屋 2, \ldots, 部屋 N と番号づけられた N 個の部屋に人が 1 人ずつ住んでおり、 また、いくつかの相異なる 2 つの部屋の間は通路によって結ばれています。 通路は M 本あり、i 本目の通路は部屋 U_i と部屋 V_i を結んでおり、長さは W_i です。

ある日(これを 0 日目とします)の夜に、部屋 A_1,A_2,\ldots, A_K に住んでいる K 人がウイルスに(新しく)感染してしまいました。 さらにその後の D 日間で i 日目 (1\leq i\leq D) には次のように感染が広がりました。

(i-1) 日目の夜の時点で感染していた人は、i 日目の夜の時点でも感染していた。
そうでない人については、(i-1) 日目の夜の時点で感染していた人の住んでいる部屋のうちの少なくとも 1 つから 距離 X_i 以内の部屋に住んでいた時かつその時に限り、新しく感染した。 ここで、部屋 P,Q の間の距離は、部屋 P から 部屋 Q まで通路のみを使って移動する時に通る通路の長さの総和としてあり得る最小値として定義される。 ただし、部屋 P から 部屋 Q へ通路のみを使って移動する事ができない時、距離は 10^{100} とする。

各 i (1\leq i\leq N) について、部屋 i に住んでいる人がそれぞれ何日目の夜に(新しく)感染したか出力してください。ただし、D 日目の夜の時点で感染していない場合は -1 を出力してください。

制約

  • 1 \leq N\leq 3\times 10^5
  • 0 \leq M\leq 3\times 10^5
  • 1 \leq U_i < V_i\leq N
  • (U_i,V_i) はすべて異なる。
  • 1\leq W_i\leq 10^9
  • 1 \leq K\leq N
  • 1\leq A_1<A_2<\cdots<A_K\leq N
  • 1 \leq D\leq 3\times 10^5
  • 1\leq X_i\leq 10^9
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N M
U_1 V_1 W_1
U_2 V_2 W_2
\vdots
U_M V_M W_M
K
A_1 A_2 \ldots A_K
D
X_1 X_2 \ldots X_D

出力

N 行出力せよ。
i 行目 (1\leq i\leq N) には、部屋 i に住んでいる人が何日目の夜に(新しく)感染したか出力せよ。

入力例 1

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

出力例 1

0
1
1
2

次のように感染は広がります。

  • 0 日目の夜、部屋 1 に住んでいる人が感染する。
  • 部屋 1 と部屋 2,3,4 の間の距離はそれぞれ 2,3,5 である。よって、X_1=3 であるから、1 日目の夜、部屋 2,3 に住んでいる人が新しく感染する。
  • 部屋 3 と部屋 4 の間の距離は 2 である。よって、X_2=3 であるから、2 日目の夜、部屋 4 に住んでいる人も感染する。

よって、部屋 1,2,3,4 に住んでいる人はそれぞれ 0,1,1,2 日目に新しく感染したため、0,1,1,2 をこの順で各行に出力します。

入力例 2

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

出力例 2

0
1
2
-1
2
0
-1

入力例 3

5 1
1 2 5
2
1 3
3
3 7 5

出力例 3

0
2
0
-1
-1

どの 2 つの部屋の間も通路のみを使って移動できるとは限らないことに注意してください。

Score : 550 points

Problem Statement

There are N rooms numbered 1, 2, \ldots, N, each with one person living in it, and M corridors connecting two different rooms. The i-th corridor connects room U_i and room V_i with a length of W_i.

One day (we call this day 0), the K people living in rooms A_1, A_2, \ldots, A_K got (newly) infected with a virus. Furthermore, on the i-th of the following D days (1\leq i\leq D), the infection spread as follows.

People who were infected at the end of the night of day (i-1) remained infected at the end of the night of day i.
For those who were not infected, they were newly infected if and only if they were living in a room within a distance of X_i from at least one room where an infected person was living at the end of the night of day (i-1). Here, the distance between rooms P and Q is defined as the minimum possible sum of the lengths of the corridors when moving from room P to room Q using only corridors. If it is impossible to move from room P to room Q using only corridors, the distance is set to 10^{100}.

For each i (1\leq i\leq N), print the day on which the person living in room i was newly infected. If they were not infected by the end of the night of day D, print -1.

Constraints

  • 1 \leq N\leq 3\times 10^5
  • 0 \leq M\leq 3\times 10^5
  • 1 \leq U_i < V_i\leq N
  • All (U_i,V_i) are different.
  • 1\leq W_i\leq 10^9
  • 1 \leq K\leq N
  • 1\leq A_1<A_2<\cdots<A_K\leq N
  • 1 \leq D\leq 3\times 10^5
  • 1\leq X_i\leq 10^9
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
U_1 V_1 W_1
U_2 V_2 W_2
\vdots
U_M V_M W_M
K
A_1 A_2 \ldots A_K
D
X_1 X_2 \ldots X_D

Output

Print N lines.
The i-th line (1\leq i\leq N) should contain the day on which the person living in room i was newly infected.

Sample Input 1

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

Sample Output 1

0
1
1
2

The infection spreads as follows.

  • On the night of day 0, the person living in room 1 gets infected.
  • The distances between room 1 and rooms 2,3,4 are 2,3,5, respectively. Thus, since X_1=3, the people living in rooms 2 and 3 are newly infected on the night of day 1.
  • The distance between rooms 3 and 4 is 2. Thus, since X_2=3, the person living in room 4 also gets infected on the night of day 2.

Therefore, the people living in rooms 1,2,3,4 were newly infected on days 0,1,1,2, respectively, so print 0,1,1,2 in this order on separate lines.

Sample Input 2

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

Sample Output 2

0
1
2
-1
2
0
-1

Sample Input 3

5 1
1 2 5
2
1 3
3
3 7 5

Sample Output 3

0
2
0
-1
-1

Note that it is not always possible to move between any two rooms using only corridors.