Problem Statement

　umg tours is planning tours across $N$ spots. There are $M$ roads, and road $i$ bidirectionally connects two distinct spots $a_i$ and $b_i$ with distance $c_i$. It is guaranteed that any two spots can be reached from each other via the roads. Also, there are never two or more roads connecting the same pair of spots.
　umg has planned $N$ tours. In tour $i$, one starts from spot $1$, moves along the roads to visit spot $i$, and then returns to spot $1$. The outbound and return routes may differ.
　One day, $N$ tourists came to use umg tours. Tourist $i$ takes part in tour $i$. Since the tourists are VIPs, each of them may, only once during each tour, use a tourist ticket to make the travel distance of any one road of their choice $0$. Note that this does not mean a road's distance can be made $0$ throughout the tour.
　For every $i\ (1\le i \le N)$, find the minimum travel distance of tourist $i$.

Notes

　Since the input and output are large, be careful about the time limit. Python users should submit with PyPy3. AC has been confirmed with PyPy3.

Input

$N\ M$
$a_1\ b_1\ c_1$
$\vdots$
$a_{M}\ b_{M}\ c_{M}$

$2\le N \le 10^5$
$N-1\le M \le \min (2\times 10^5,N(N-1)/2)$
$1\le a_i,b_i \le N$
$1\le c_i \le 10^9$
When $i\neq j$, $(a_i,b_i)\neq (a_j,b_j)$ and $(a_i,b_i)\neq (b_j,a_j)$.
The given graph is connected.
All values in the input are integers.

Output

Print $N$ lines. On the $i$-th line, print the minimum travel distance of tourist $i$. Print a newline at the end.

Sample

5 6
1 2 2
1 3 3
1 4 4
2 5 10
3 5 7
4 5 8

0
2
3
4
12

6 8
1 2 5
2 6 8
1 3 3
3 5 2
5 6 1
1 4 6
4 5 2
1 6 10

0
5
3
6
6
6