시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 10 5 3 50.000%

문제

A weighted tree is a tree where each edge is labeled with a number representing the edge's length. All lengths are positive. For each node, you have to find the maximum possible distance to any other node in the tree.

입력

The input file contains the description of the tree. The first line of the input file contains one integer N, 2<=N<=50000. Each of the following (N-1) lines contains the description of the tree’s edges. Each edge is described by three positive integers. The first two integers are the labels of the nodes connected by this edge, ranging from 1 to N, the third number – the length of the edge. The total length of all edges does not exceed 231 -1. It is guaranteed that the file contains a correct description of the tree.

출력

The output consists of exactly N lines: the k-th line contains the distance from node k (k=1..N ) to the most distant node.

예제 입력

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

예제 출력

5
9
10
10
8
6

힌트