EJOI-land 是一个由 $N$ 个城市组成的王国。每个城市都有一个唯一的编号，范围在 $1$ 到 $N$ 之间。城市之间由 $N-1$ 条双向道路连接。保证任意两个城市之间都是连通的，换句话说，EJOI-land 的结构是一棵树。EJOI-land 中还有 $K$ 个贸易条约。每个条约由一对城市 $(A, B)$ 定义，并关联一个成本 $C$。

国王决定通过以下方式测试他儿子的治理能力：

• 他将选择一个城市 $H$ 并将其指定为王子的总部。假设此时树以 $H$ 为根。
• 王子将选择至多两个 $H$ 的邻居城市。现在，$H$ 以及所选邻居城市的子树都在他的管辖之下。

他获得的利润等于其管辖范围内所有条约的成本 $C$ 之和。若要使一个条约处于他的管辖范围内，该条约关联的两个城市都必须在他的管辖之下。

国王尚未宣布哪个城市将成为王子的总部，但王子对此感到好奇。因此，对于每个城市，他想知道如果将其选为总部，他能获得的最大利润是多少。

你的任务是求出每个城市对应的最大利润。

输入格式

第一行包含两个空格分隔的整数 $N$ 和 $K$，分别表示 EJOI-land 的城市数量和贸易条约的数量。

接下来的 $N-1$ 行，每行包含两个空格分隔的整数 $U$ 和 $V$，表示城市 $U$ 和 $V$ 之间有一条道路。

接下来的 $K$ 行，每行包含三个空格分隔的整数 $A$、$B$ 和 $C$，分别表示条约涉及的两个城市及其成本。

输出格式

输出 $N$ 个空格分隔的整数，其中第 $i$ 个整数表示如果选择城市 $i$ 作为王子总部时可获得的最大利润。

样例

样例输入 1

6 4
6 2
2 5
3 6
1 2
4 6
2 5 11
5 6 16
4 3 18
2 3 6

样例输出 1

51 51 51 51 51 33

说明

当以第 $6$ 号城市作为总部时，王子有三种选择两个邻居城市及其各自子树的方式：

• 城市 $2$ 和 $3$
• 城市 $2$ 和 $4$
• 城市 $3$ 和 $4$

通过选择管辖城市 $2$ 和 $3$，王子将条约 $1$、$2$ 和 $4$ 纳入其管辖范围。因此，他获得的利润为 $11 + 16 + 6 = 33$。

数据范围

• $2 \le N, K \le 2 \cdot 10^5$
• $1 \le U, V, A, B \le N$
• $1 \le C \le 10^6$

子任务