题目描述

题目译自 eJOI2024 Day1 T1. Many Pairs

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

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

• 他将选择一个城市 $H$ 作为王子的总部。假设这棵树现在以 $H$ 为根节点。
• 王子将选择最多两个与 $H$ 相邻的城市。将 $H$ 及其所选城市的子树都归于他的治理之下。

王子获得的利润等于其管辖范围内的条约的成本 $C$ 的总和。对于一个条约来说，只有当它涉及的两个城市都在王子的管辖范围内时，它才在他的管辖范围内。

国王还没有宣布哪个城市将成为王子的总部，但王子仍然喜欢猜测。因此，对于每个城市，他想知道如果它被选为新的总部，他可以获得的最大利润是多少。

你的任务是找到每个城市的最大利润。

输入格式

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

接下来的 $N-1$ 行中，每行包含两个用空格分隔的整数 $U$ 和 $V$，表示城市 $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$，条约 $1, 2, 4$ 将在王子的管辖范围内。因此，他获得的利润为 $11+16+6=33$。

数据范围与提示

对于所有输入数据，满足：

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

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$12$	$N, K \leq 50$
$2$	$13$	$N \leq 5000, K \leq 500$
$3$	$17$	$N \leq 5000, K \leq 2000$
$4$	$21$	$N, K \leq 5000$
$5$	$37$	无附加限制