题目描述

深绘里一直很讨厌雨天。

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

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

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

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

有 $\red {n}$ 个点，形成一个树状结构。

有 $\red {m}$ 次发放操作，每次选择两个点 $\red {x,y}$，对 $\red {x}$ 到 $\red {y}$ 的路径上（包括 $\red {x,y}$）的每个点发放一袋 $\red {z }$类型的物品。

求完成所有发放操作后，每个点存放最多的是哪种类型的物品。

输入格式

第一行两个正整数$\red {n,m}$，含义如题目所示。

接下来$\red {n-1}$行，每行两个数$\red {(a,b)}$，表示$\red {(a,b)}$间有一条边。

再接下来$\red {m}$行，每行三个数$\red {(x,y,z)}$，含义如题目所示。

输出格式

共$\red {n}$行，第$\red {i}$行一个整数，表示第$\red i$座房屋里存放的最多的是哪种救济粮，如果有多种救济粮存放次数一样，输出编号最小的。

如果某座房屋里没有救济粮，则对应一行输出$\red {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

提示

$\red {1≤n,m≤100000}$,

$\red {1≤z≤10^9}$