Farthest node in a weighted tree

Interview

Time limit1sMemory limit256 MB

Summary

For every node of a weighted tree with up to 50000 nodes, print its distance to the farthest node.

Level: Medium6 of 10
Topics: Tree, DFS
Solved: No attempts yet

Problem

A weighted tree is a tree where every edge carries a number giving that edge's length. All lengths are positive.

For each node of the tree, find the largest distance from that node to any other node. The distance between two nodes is the sum of the edge lengths along the path that joins them.

Input

The first line contains the number of nodes $N$ . ( $2 \le N \le 50000$ )

Each of the next $N-1$ lines describes one edge with three positive integers. The first two are the labels of the nodes the edge joins (from $1$ to $N$ ), and the third is the length of the edge. The total length of all edges does not exceed $2^{31}-1$ . The input always describes a valid tree.

Output

Print exactly $N$ lines. The $k$ -th line contains the distance from node $k$ to the node farthest from it. ( $k = 1, 2, \dots, N$ )

Examples4

Example 1

Input

Expected output

Example 2
Input
```
2
1 2 7
```
Expected output
```
7
7
```
Example 3
Input
```
5
1 2 4
2 3 1
3 4 6
4 5 2
```
Expected output
```
13
9
8
11
13
```

Example 4

Input

Expected output