配点 : $700$ 点

問題文

イカはグラフの頂点に色を塗るのが好きです。

$1$ から $N$ までの番号がついた $N$ 個の頂点と $M$ 本の辺からなる単純無向グラフが与えられます。 全ての頂点ははじめ、色 $0$ で塗られています。$i$ 番目の辺は頂点 $a_i$ と頂点 $b_i$ を双方向につなぐ長さ $1$ の辺です。

イカはこのグラフに対して $Q$ 回の操作を行いました。 $i$ 回目の操作では、頂点 $v_i$ から距離 $d_i$ 以内にあるような頂点たち全ての色を色 $c_i$ で上書きしました。

$Q$ 回の操作後において、各頂点がどの色で塗られているか調べてください。

制約

• $1 \leq N,M,Q \leq 10^5$
• $1 \leq a_i,b_i,v_i \leq N$
• $a_i \neq b_i$
• $0 \leq d_i \leq 10$
• $1 \leq c_i \leq 10^5$
• $d_i, c_i$ いずれも整数
• 与えられるグラフに自己ループや多重辺は存在しない

部分点

• $1 \leq N,M,Q \leq 2{,}000$ を満たすデータセットに正解した場合は、部分点として $200$ 点が与えられる。

入力

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

$N$ $M$

$a_1$ $b_1$

$:$

$a_{M}$ $b_{M}$

$Q$

$v_1$ $d_1$ $c_1$

$:$

$v_{Q}$ $d_{Q}$ $c_{Q}$

出力

答えを $N$ 行に出力せよ。 $i$ 行目では $Q$ 回の操作後における頂点 $i$ の色を出力せよ。

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

2
2
2
2
2
1
0

はじめ、各頂点は色 $0$ で塗られています。 $1$ 回目の操作により、頂点 $5,6$ が色 $1$ で塗られます。 $2$ 回目の操作により、頂点 $1,2,3,4,5$ が色 $2$ で塗られます。

14 10
1 4
5 7
7 11
4 10
14 7
14 3
6 14
8 11
5 13
8 3
8
8 6 2
9 7 85
6 9 3
6 7 5
10 3 1
12 9 4
9 6 6
8 2 3

1
0
3
1
5
5
3
3
6
1
3
4
5
3

与えられるグラフは連結とは限りません。