Problem Statement

Squid loves painting vertices in graphs.

There is a simple undirected graph consisting of $N$ vertices numbered $1$ through $N$, and $M$ edges. Initially, all the vertices are painted in color $0$. The $i$-th edge bidirectionally connects two vertices $a_i$ and $b_i$. The length of every edge is $1$.

Squid performed $Q$ operations on this graph. In the $i$-th operation, he repaints all the vertices within a distance of $d_i$ from vertex $v_i$, in color $c_i$.

Find the color of each vertex after the $Q$ operations.

Constraints

• $1 ≤ N,M,Q ≤ 10^5$
• $1 ≤ a_i,b_i,v_i ≤ N$
• $a_i ≠ b_i$
• $0 ≤ d_i ≤ 10$
• $1 ≤ c_i ≤10^5$
• $d_i$ and $c_i$ are all integers.
• There are no self-loops or multiple edges in the given graph.

Partial Score

• $200$ points will be awarded for passing the testset satisfying $1 ≤ N,M,Q ≤ 2{,}000$.

Input

Input is given from Standard Input in the following format:

N M
a_1 b_1
:
a_{M} b_{M}
Q
v_1 d_1 c_1
:
v_{Q} d_{Q} c_{Q}

Output

Print the answer in $N$ lines. In the $i$-th line, print the color of vertex $i$ after the $Q$ operations.