Village Relief Distribution

Given a village with n houses that form a tree structure, there are m rounds of relief food distribution. In each round, you are provided with three integers \(x\), \(y\), and \(z\). For that round, every house on the unique path between house \(x\) and house \(y\) (inclusive) receives one bag of relief food of type \(z\).

After all distributions, for each house, determine which type of relief food appears most frequently. In case of a tie, output the smallest relief food type.

Note: The tree structure guarantees that there is exactly one simple path between any two houses.

inputFormat

The first line contains two integers \(n\) and \(m\) --- the number of houses and the number of distribution rounds respectively.

The next \(n-1\) lines each contain two integers \(u\) and \(v\) representing an edge between houses \(u\) and \(v\) in the tree.

The following \(m\) lines each contain three integers \(x\), \(y\), and \(z\), indicating that in this round, every house on the unique path from \(x\) to \(y\) (inclusive) receives one bag of relief food of type \(z\).

outputFormat

Output a single line containing \(n\) integers. The \(i\)th integer denotes the relief food type that appears most frequently in house \(i\) after all distributions. If there is a tie, output the smallest relief food type among those tied.

sample

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

10 10 10 10 10