Given a weighted tree with $N$ vertices and $N - 1$ edges. Let $D(i,j)$ be the distance of the unique simple path from $i$ to $j$ in this tree (i.e., the path from $i$ to $j$ that will not visit any node more than once).

We construct a new directed graph with $N$ vertices, for each pair of vertices $(i,j)$ if $i < j$ we add an edge from $i$ to $j$ with weight $D(i,j)$.

Find the shortest path from $1$ to all other vertices in the newly constructed graph.

$\textbf{Input}$

The first line contains one integer - $N (2 \le N \le 8 \cdot 10^4)$

The $(i + 1)^{th} (1 \le i \le N - 1)$ line contains three integers - $u_i, v_i, w_i (1 \le u_i < v_i \le N, |w_i| \le 10^9)$, meaning there is an edge with cost $w_i$ between vertices $u_i$ and $v_i$. These edges describe the original tree.

$\textbf{Output}$

Output $N$ integers, the $i^{th}$ integer represents the shortest path from $1$ to $i$.