Tree

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.

Input

Contains the description of the tree. The first line contains the number of vertices $n(2\le n\le 50000)$ in a tree. 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 $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=\mathrm{1...}n)$ to the most distant node.

Examples