0x60图论（0x63 树的直径与最近公共祖先）例题5：雨天的尾巴

【题意】

给定一棵有 $n$ 节点的无根树。

有 $m$ 次操作，每次操作给出三个整数 $(x, y, z)$，表示点 $x$ 到 点 $y$ 的路径上（含 $x$ 和 $y$）每个点都发放一个 $z$ 类型的球。

当所有操作完毕后，求每个点里存放的最多的是哪种类型的求。

【输入格式】

第一行是两个正整数$n \ m$。

下来 $n-1$ 行，每行两个整数 $a, b$，代表存在一条连接点 $a$ 和 $b$ 的边。

下来 $m$ 行，每行三个整数 $x, y, z$。

【输出格式】

输出 $n$ 行，每行一个整数，第 $i$ 行的整数代表 $i$ 号点存放最多的球的类型，如果有多种球都是存放最多的，输出类型编号最小的一种。

如果某个点没有球，则输出 $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

【提示】

• 对于 $20\%$ 的数据，保证 $n, m \leq 100$。

• 对于 $50\%$ 的数据，保证 $n, m \leq 2 \times 10^3$。

• 对于 $100\%$ 测试数据，保证 $1 \leq n, m \leq 10^5$，$1 \leq a,b,x,y \leq n$，$1 \leq z \leq 2^{31}-1$。