深绘里一直很讨厌雨天。
灼热的天气穿透了前半个夏天，后来一场大雨和随之而来的洪水，浇灭了一切。
虽然深绘里家乡的小村落对洪水有着顽固的抵抗力，但也倒了几座老房子，几棵老树被连根拔起，以及田地里的粮食被弄得一片狼藉。
无奈的深绘里和村民们只好等待救济粮来维生。
不过救济粮的发放方式很特别。

首先村落里的一共有 n 座房屋，并形成一个树状结构。然后救济粮分 m 次发放，每次选择两个房屋 (x,y)，然后对于 x 到 y 的路径上（含 x 和 y）每座房子里发放一袋 z 类型的救济粮。
然后深绘里想知道，当所有的救济粮发放完毕后，每座房子里存放的最多的是哪种救济粮。

输入的第一行是两个用空格隔开的正整数，分别代表房屋的个数 n 和救济粮发放的次数 m。
第 2 到 第 n 行，每行有两个用空格隔开的整数 a,b，代表存在一条连接房屋 a 和 b 的边。
第 (n+1) 到第 (n+m) 行，每行有三个用空格隔开的整数 x,y,z，代表一次救济粮的发放是从 x 到 y 路径上的每栋房子发放了一袋 z 类型的救济粮。

输出 n 行，每行一个整数，第 i 行的整数代表 i 号房屋存放最多的救济粮的种类，如果有多种救济粮都是存放最多的，输出种类编号最小的一种。
如果某座房屋没有救济粮，则输出 0。

• 对于 20% 的数据，保证 n,m≤100。
• 对于 50% 的数据，保证 n,m≤2×10³。
• 对于 100% 测试数据，保证 1≤n,m≤10⁵， 1≤a,b,x,y≤n， 1≤z≤10⁵。

P4556 算法 数据结构 线段树 树状数组