colouring

Title

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 ai and bi. 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 di from vertex vi, in color ci.

Find the color of each vertex after the Q operations.

Constraints

  • 1 ≤ N,M,Q ≤ 105
  • 1 ≤ ai,bi,vi ≤ N
  • ai ≠ bi
  • 0 ≤ di ≤ 10
  • 1 ≤ ci ≤105
  • di and ci are all integers.
  • There are no self-loops or multiple edges in the given graph.

Subtasks

  • Subtask 1 (30%): 1 ≤ N,M,Q ≤ 2000
  • Subtask 2 (70%): No other constraints
  • Subtask 3 (0%): Sample Testcases

Input

Input is given from Standard Input in the following format:

N M
a1 b1
:
aM bM
Q
v1 d1 c1
:
vQ dQ cQ

Output

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

Sample Input 1

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

Sample Output 1

2
2
2
2
2
1
0

Initially, each vertex is painted in color 0. In the first operation, vertices 5 and 6 are repainted in color 1. In the second operation, vertices 1, 2, 3, 4 and 5 are repainted in color 2. 2ab7e180230b159d42d35ea7e555b3b0.png

Sample Input 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

Sample Output 2

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

The given graph may not be connected.


Submitting .cpp to 'colouring'


You're not logged in! Click here to login

Time Limit: 1 Seconds
Memory Limit: 1024MB
No. of ACs: 5
Your best score: 0
Source: AGC 012B

Subtask Score
1 30
2 70
3 0