問題文

部屋 $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$ つの部屋の間も通路のみを使って移動できるとは限らないことに注意してください。