分数: 800 点
问题陈述
Snuke Festival 2017 将在树上举行 N 顶点编号 1,2, ...,N。 的 i第一条边连接顶点 a_i 和 b_i,并且有 喜悦 c_i.
工作人员是 Snuke 并且 N-1 黑猫。 Snuke 将在某个顶点设立总部,并从那里向对方部署一只猫 N-1 顶点。
对于每个顶点,计算 善良 当总部设立在该顶点时。 总部设立在 Vertex 的美好 i 计算如下:
- 让 X=0.
- 对于每个整数 j 之间 1 和 N (含)除外 i,执行以下操作:
- 添加 c to X,其中 c 是从 Vertex 开始的路径上边的最小快乐度 i 到顶点 j.
- 漂亮度是最终的值 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- 当总部设置在Vertex时,第行必须包含niceness 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