暂无测试数据。

当林荫意识到他与女神 $DJ$ 绝无可能时，林荫决定从她的世界中消失。

但是消失不代表离开，林荫决定在她看不到的地方成为一个隐形守护者。

林荫动用家族势力在全国范围内修建了 $N$ 座安全屋，其间由 $N-1$ 条协作物流通道连接成为一棵树。

林荫为此次行动准备了多种装备，分 $M$ 次运输。

每次林荫会在从 $X$ 到 $Y$ 的路径上每一座安全屋中放置一件编号为 $Z$ 的装备（$Z$ 为一个正整数）。

现在林荫想知道，$M$ 次运输后,每一座安全屋中哪种装备最多（如果有安全屋中没有装备则返回 $0$，如果有安全屋中装备最多的编号有多种，则返回装备最多的最小编号）。

输入格式

第一行有两个正整数 $N$ 和 $M$。

第二行到第 $N$ 行：每行有两个正整数 $A$ 和 $B$，代表存 $A$ 与 $B$ 间存在一条协作物流道路。

第 $N+1$ 到第 $N+M$ 行：每行有三个正整数 $X,Y,Z$，代表从 $X$ 到 $Y$ 的所有安全屋各增加一件编号为 $Z$ 的装备。

输出格式

一行 $N$ 个正整数，代表第 $i$ 座房屋中最多装备的编号。

数据范围

对于 $30\%$ 的数据：$N \le 1000,M \le 10000$。

对于 $100\%$ 的数据：$M$ 以外的所有数字 $\le 10^5,M\le 5 \times 10^5$。

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

2 3 3 0 2