Problem Description

You are given a tree with $ N $ vertices numbered from $ 1 $ to $ N $. There are $ N-1 $ edges numbered from $ 1 $ to $ N-1 $, where edge $ i $ connects vertex $ a_i $ and vertex $ b_i $ bidirectionally. Each edge can be colored, and the color is represented by an integer between $ 0 $ and $ 10^5 $. Initially, all edges are colored $ 0 $.

This tree will undergo $ Q $ operations. In the $ i $-th operation, all edges on the shortest path between vertex $ u_i $ and vertex $ v_i $ will be overwritten with color $ c_i $.

After $ Q $ operations, determine the color of each edge $1, 2, \ldots, N-1$.

Input Format

The input is given from the standard input in the following format:

$ N $ $ Q $ $ a_1 $ $ b_1 $ $\vdots$ $ a_{N-1} $ $ b_{N-1} $ $ u_1 $ $ v_1 $ $ c_1 $ $\vdots$ $ u_Q $ $ v_Q $ $ c_Q $

Output Format

Output $ N-1 $ lines. The $ i $-th line should contain the color of edge $ i $.

Sample Input and Output

Sample Input #1

4 2
1 2
1 3
2 4
2 3 10
1 2 5

Sample Output #1

5
10
0

Sample Input #2

10 10
7 2
5 8
8 6
8 3
8 9
9 1
4 8
4 10
8 7
7 5 12773
2 6 74733
1 6 64470
7 2 41311
1 9 39776
4 8 71709
9 1 23551
4 6 29181
3 7 23742
8 4 54686

Sample Output #2

41311
12773
29181
23742
64470
23551
54686
0
23742

Notes/Hints

Constraints

• All given inputs are integers.
• $2 \leq N \leq 10^5$
• $1 \leq Q \leq 10^5$
• $1 \leq a_i, b_i, u_i, v_i \leq N$
• $u_i \neq v_i$
• $1 \leq c_i \leq 10^5$
• The given graph is a tree.

Sample Explanation 1

• Initially, all edges are colored $ 0 $.
• In the first operation, edges $ 1 $ and $ 2 $ are overwritten with color $ 10 $.
• In the second operation, edge $ 1 $ is overwritten with color $ 5 $.
• Finally, edges $ 1, 2, 3 $ are colored $ 5, 10, 0 $ respectively.

见题面 Input 部分

见题面 Output 部分