题目描述

EJOI 大陆由 $N$ 个城市组成，这些城市用 $1 \sim N$ 来编号。城市之间有 $N-1$ 条双向道路连接，且保证你可以从任意一个城市到达另外一个城市。换句话说，EJOI 大陆是一个树形结构。

在这个大路上还有 $K$ 个贸易关系，用城市对 $(A,B)$ 和利润 $C$ 来表示。

现在，EJOI 大陆的国王想通过以下方式测试王子的执政能力：

• 首先，国王会选择一个城市 $H$ 作为首都。现在，这棵树以 $H$ 为根。

• 接下来，王子可以选择至多两个和 $H$ 相邻的城市。现在，$H$ 城以及以被选中城市为根的子树中的所有城市都在王子的管辖下。

选择完毕后，他的利润就等于他管辖的这些城市中的贸易关系的利润之和。注意：当且仅当贸易关系双方都在王子管辖下，这个贸易关系的利润才可以归王子。

现在国王还没有选好令哪个城市作为首都。但是王子很好奇，他想知道，对于每个城市，如果其作为首都，那么他可以获得的最大利润是多少。

输入格式

第一行，两个正整数 $N,K$。

接下来 $N-1$ 行，每行两个整数 $U$ 和 $V$，表示大陆上的双向道路。

接下来 $K$ 行，每行三个整数 $A,B,C$，表示贸易关系。

输出格式

输出一行 $N$ 个整数，第 $i$ 个表示如果让第 $i$ 个城市作为首都，那么王子可以获得的最大利润。

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

51 51 51 51 51 33

提示

【样例解释】

以 $6$ 号城市作为首都为例，他可以选择以下城市：

• $2$ 和 $3$

• $2$ 和 $4$

• $3$ 和 $4$

其中，选择 $2$ 和 $3$ 号城市可以得到最大利润 $11+16+6=33$。

【数据范围】

本题采用 $\text{Subtask}$ 捆绑测试。

对于 $100\%$ 的数据：

• $2 \le N,K \le 2 \times 10^5$

• $1 \le U,V,A,B \le N$

• $1 \le C \le 10^6$