Tree — Eolymp

Input

Contains the description of the tree. The first line contains the number of vertices $n (2 \leq n \leq 50000)$ n~(2 \le n \le 50000) in a tree. Each of the following $n - 1$ 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 $2^{31} - 1$ 2^{31} - 1. It is guaranteed that the description of the tree is correct.

Output

Print exactly $n$ lines: the $k$ -th line contains the distance from node $k (k = 1... n)$ k~(k = 1...n) to the most distant node.

Examples

Example 1

Loading