题目描述

某地铁系统由 $N$ 个站点组成，站点之间通过 $N-1$ 条双向线路连接，并保证任意两个站点之间都可以互相到达。因此，整个地铁线路结构是一棵树。

此外，系统中有 $M$ 列地铁。每列地铁都有一条线性路线，从某个站点出发，沿树上的唯一路径到达另一个站点。每列地铁都有一个编号。

每个站点都有一块信息显示屏，上面按编号从小到大显示所有经过该站点的地铁编号。对于显示屏上的一个列表

某位病人总会忍不住计算下标为偶数的位置上的编号之和：

请你对每个站点计算这个值。

输入格式

第一行包含两个整数 $N,M$。

接下来 $N-1$ 行，每行包含两个整数 $x_i,y_i$，表示站点 $x_i$ 与站点 $y_i$ 之间有一条双向线路。

接下来 $M$ 行，每行包含三个整数 $a_i,b_i,o_i$，表示编号为 $o_i$ 的地铁从站点 $a_i$ 出发，沿树上的唯一路径到达站点 $b_i$。

输出格式

包含 $N$ 行。

第 $i$ 行输出一个整数，表示第 $i$ 个站点显示屏上，按编号升序排列后，下标为偶数的地铁编号之和。

如果没有任何地铁经过站点 $i$，则输出 0。

约束

• $1 \le N \le 200000$。
• $1 \le M \le 200000$。
• 对所有 $1\le i\le M$，有 $1 \le o_i \le M$。
• 保证任意两个站点之间均可达。

样例

输入

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

输出

2
4
2
1
1
3

样例解释

各站点显示屏上的地铁编号列表如下：

站点 1: 2 4
站点 2: 1 2 3 4
站点 3: 2
站点 4: 1 2
站点 5: 1 3
站点 6: 3

列表下标从 $0$ 开始，因此需要累加第 $0,2,4,\ldots$ 个元素。