#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

### 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 `a _{i}` and

`b`. The length of every edge is

_{i}`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`, in color

_{i}`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`and_{i}`c`are all integers._{i}- 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:

NMa_{1}b_{1}:a_{M}b_{M}Qv_{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.

### 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`.

### 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.

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 30 | 13 | 1s | 256MB | Minimum |

2 | 70 | 33 | 1s | 256MB | Minimum |

3 | 0 | 2 | 1s | 256MB | Minimum |

### Judge Compile Command

g++-8 ans.cpp -o colouring -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512