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$$.