Description

There are $n$ houses in the village, forming a tree. Relief rations are distributed $m$ times. Each time, two houses $(x, y)$ are chosen. For every house on the path from $x$ to $y$ (including $x$ and $y$), one bag of type $z$ relief rations is given.

After all distributions are finished, Shenhuili wants to know, for each house, which type of relief rations is stored the most.

Input Format

The first line contains two positive integers $n$ and $m$.

Lines $2$ through $n$ each contain two integers $a, b$, indicating that there is an edge between houses $a$ and $b$.

Lines $(n + 1)$ through $(n + m)$ each contain three integers $x, y, z$, indicating that in one distribution, every house on the path from $x$ to $y$ receives one bag of type $z$ relief rations.

Output Format

Output $n$ lines. The integer on the $i$-th line is the type of relief rations that appears most in house $i$. If multiple types are tied for the maximum, output the smallest type id.

If a house has no relief rations, output 0.

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

2
3
3
0
2

Hint

• For $20\%$ of the testdata, it is guaranteed that $n, m \leq 100$.
• For $50\%$ of the testdata, it is guaranteed that $n, m \leq 2 \times 10^3$.
• For $100\%$ of the testdata, it is guaranteed that $1 \leq n, m \leq 10^5$, $1 \leq a, b, x, y \leq n$, and $1 \leq z \leq 10^5$.

Translated by ChatGPT 5