题目描述
深绘里一直很讨厌雨天。
灼热的天气穿透了前半个夏天，后来一场大雨和随之而来的洪水，浇灭了一切。
虽然深绘里家乡的小村落对洪水有着顽固的抵抗力，但也倒了几座老房子，几棵老树被连根拔起，以及田地里的粮食被弄得一片狼藉。
无奈的深绘里和村民们只好等待救济粮来维生。
不过救济粮的发放方式很特别。
有 n 个点，形成一个树状结构。
有 m 次发放操作，每次选择两个点 x,y，对 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
提示
数据范围
1≤n,m≤100000
1≤z≤109