题目描述

前段时间，学校购买了第一台电脑（因此这台电脑的ID为1）。近年来，学校又购买了N-1台新电脑。每台新电脑都连接到之前安装好的一台电脑上。 学校管理人员对网络运行缓慢感到担忧，并想知道第i台电脑需要发送信号的最大距离Si（即到最远电脑的电缆长度）。你需要提供这一信息。 提示：示例输入与这张图相对应。从图中可以看出，计算机4是离1号计算机最远的，所以S1=3。计算机4和5是离2号计算机最远的，所以S2=2。 计算机5是离3号计算机最远的，所以S3=3。我们还得到S4=4，S5=4。

输入格式

第一行是一个自然数N（N<=10000），后面是(N-1)行，每行描述一台计算机。 第i行包含三个自然数：第i台计算机连接的计算机编号和用于连接的电缆长度。电缆长度不超过10^9。输入行中的数字用空格分隔。

输出格式

输出N行。第i行是第i台计算机需要发送信号的最大距离Si（1<=i<=N）。

样例

输入样例 1

5
2 1 1
3 2 1
4 3 1
5 1 1

输出样例 1

3
2
3
4
4

输入样例 2

10
10 9 1000000000
9 8 1000000000
8 7 1000000000
7 6 1000000000
6 5 1000000000
5 4 1000000000
4 3 1000000000
3 2 1000000000
2 1 1000000000

输出样例 2

9000000000
8000000000
7000000000
6000000000
5000000000
5000000000
6000000000
7000000000
8000000000
9000000000

输入样例 3

9
1 4 3
1 2 3
1 3 7
2 5 1
2 6 8
3 7 3
3 8 2
7 9 2

输出样例 3

12
15
18
15
16
23
21
20
23

提示

分析：给定一棵节点为 N 的树（1≤N ≤10000），输出每个节点 i 到 离 i 最远的节点的长度。 离每一个节点 i 最远的点就是树的直径的两端的节点 u 和 v 。 于是，我们可以用 两次 DFS 先将树的直径的两个端点u、v求出来，其中第二次 DFS 可以得到 dis(u->i)。 再从v开始进行第三次 DFS，求出每个节点到v的距离dis(v->i)。 对于节点 i ，它的答案就是： max(dis(u->i),dis(v->i))