3380. 雨天的尾巴

【题目描述】

深绘里一直很讨厌雨天。

灼热的天气穿透了前半个夏天，后来一场大雨和随之而来的洪水，浇灭了一切。

虽然深绘里家乡的小村落对洪水有着顽固的抵抗力，但也倒了几座老房子，几棵老树被连根拔起，以及田地里的粮食被弄得一片狼藉。

无奈的深绘里和村民们只好等待救济粮来维生。

不过救济粮的发放方式很特别。

首先村落里的一共有 $n$ 座房屋，并形成一个树状结构。然后救济粮分 $m$次发放，每次选择两个房屋 $(x, y)$，然后对于$x$到$y$的路径上(含$x$和$y$)每座房子里发放一袋$z$类型的救济粮。

然后深绘里想知道，当所有的救济粮发放完毕后，每座房子里存放的最多的是哪种救济粮(如果有房屋没有收到救济粮则记为0)。

【输入格式】

输入的第一行是两个用空格隔开的正整数，分别代表房屋的个数$n$和救济粮发放的次数$m$。

第2到第$n$行，每行有两个用空格隔开的整数$a, b$，代表存在一条连接房屋$a$和$b$的边。

第$n+1$ 到第 $n+m$ 行，每行有三个用空格隔开的整数 $x, y, z$，代表一次救济粮的发放是从 $x$ 到 $y$ 路径上的每栋房子发放了一袋 $z$ 类型的救济粮。

【输出格式】

输出共$n$行，每行一个整数，第$i$行整数代表第$i$座房屋收到最多救济粮的种类。

如果有多个救济粮满足条件，则输出最小的。

【样例输入】

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

【样例输出】

2
3
3
0
2

【数据范围与约定】

$1\leq n,m\leq 10^5,1\leq a,b,x,y\leq n,1\leq z\leq 10^9$

【来源】

洛谷P4556&BZOJ3307