问题描述

Snuke Festival 2017 将在一棵有 $N$ 个编号为 $1,2,...,N$ 的顶点的树上举行。第 $i$ 条边连接顶点 $a_i$ 和 $b_i$，具有 愉悦度 $c_i$。

工作人员包括 Snuke 和 $N-1$ 只黑猫。Snuke 将在某个顶点设置总部，并从那里派遣一只猫到其他 $N-1$ 个顶点。

对于每个顶点，计算在该顶点设置总部时的 美好程度。当在顶点 $i$ 设置总部时，美好程度的计算方法如下：

• 令 $X=0$。
• 对于 $1$ 到 $N$（包括 $i$）之间的每个整数 $j$，执行以下操作：
  • 将从顶点 $i$ 到顶点 $j$ 路径上愉悦度最小的边的愉悦度 $c$ 加到 $X$ 中。
• 美好程度就是 $X$ 的最终值。

约束条件

• $1 \leq N \leq 10^{5}$
• $1 \leq a_i,b_i \leq N$
• $1 \leq c_i \leq 10^{9}$
• 给定的图是一棵树。
• 所有输入值都是整数。

部分得分

• 在价值 $200$ 分的测试数据中，$N \leq 1000$。
• 在价值 $200$ 分的测试数据中，$c_i \leq 2$。

输入

输入以以下格式从标准输入给出：

$N$

$a_1$ $b_1$ $c_1$

:

$a_{N-1}$ $b_{N-1}$ $c_{N-1}$

输出

输出 $N$ 行。第 $i$ 行必须包含在顶点 $i$ 设置总部时的美好程度。

示例输入 1

3
1 2 10
2 3 20

示例输出 1

20
30
30

• 下图显示了当总部设置在每个顶点 $1$、$2$ 和 $3$ 时的情况。
• 边上的数字表示边的愉悦度，顶点下方的数字表示从总部到该顶点路径上愉悦度最小的边的愉悦度。

示例输入 2

15
6 3 2
13 3 1
1 13 2
7 1 2
8 1 1
2 8 2
2 12 2
5 2 2
2 11 2
10 2 2
10 9 1
9 14 2
4 14 1
11 15 2

示例输出 2

16
20
15
14
20
15
16
20
15
20
20
20
16
15
20

示例输入 3

19
19 14 48
11 19 23
17 14 30
7 11 15
2 19 15
2 18 21
19 10 43
12 11 25
3 11 4
5 19 50
4 11 19
9 12 29
14 13 3
14 6 12
14 15 14
5 1 6
8 18 13
7 16 14

示例输出 3

103
237
71
263
370
193
231
207
299
358
295
299
54
368
220
220
319
237
370