[Vani有约会]雨天的尾巴 /【模板】线段树合并

题目背景

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

题目描述

首先村落里的一共有 $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$。

输入输出样例

输入样例 #1

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

输出样例 #1

2
3
3
0
2

说明

- 对于 $20\%$ 的数据,保证 $n, m \leq 100$。 - 对于 $50\%$ 的数据,保证 $n, m \leq 2 \times 10^3$。 - 对于 $100\%$ 测试数据,保证 $1 \leq n, m \leq 10^5$,$1 \leq a,b,x,y \leq n$,$1 \leq z \leq 10^5$。