AT_abc307_f [ABC307F] Virus 2

[problemUrl]: https://atcoder.jp/contests/abc307/tasks/abc307_f 部屋 $ 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 $ を出力してください。

入力は以下の形式で標準入力から与えられる。 > $ 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\ \leq\ N\leq\ 3\times\ 10^5 $ - $ 0\ \leq\ M\leq\ 3\times\ 10^5 $ - $ 1\ \leq\ U_i\