题目描述

给你一个包含 $n$ 个节点的有根树。树上节点编号从 $1$ 到 $n$。根节点编号为 $1$。

树上的第 $i(1 \le i \le n-1)$ 条边连接节点 $u_i$ 和 $v_i$，长度为 $w_i$。

对于树上的每一个节点 $u$，请你回答：

• 经过节点 $u$ 的所有路径中，最长的那条路径的长度。

输入格式

第一行，一个整数 $n(1 \le n \le 10^5)$。

接下来 $n-1$ 行，每行包含三个整数 $u_i$，$v_i$ 和 $w_i$，表示第 $i$ 条边连接节点 $u_i$ 和 $v_i$，它的长度是 $w_i$。

输出格式

输出共 $n$ 行，每一行包含一个整数。

其中，第 $i$ 行的整数表示经过节点 $i$ 的最长路径长度。

样例

4
1 2 1
1 3 2
1 4 3

5
4
5
5

7
1 2 3
1 3 2
2 4 1
3 6 15
3 7 6
5 2 10

30
30
36
21
30
36
21

说明/提示

数据规模与约定

• 对于 $20\%$ 的数据，$n \le 10$，$1 \le w_i \le 10$；
• 对于 $40\%$ 的数据，$n \le 1000$，$1 \le w_i \le 1000$；
• 对于 $100\%$ 的数据，$1 \le n \le 10^5$，$1 \le w_i \le 10^9$。