問題文

　umg toursでは，$N$個のスポットでのツアーを企画しています。道が$M$個あり，道$i$は，異なる2つのスポット$a_i$と$b_i$の間を距離$c_i$で双方向に結んでいます。 どの2つのスポット間も道を経由することで行き来できることが保証されます。また，同じスポットを結ぶ道が2本以上存在することもありません。
　umgくんは$N$個のツアーを企画しました。ツアー$i$では，スポット$1$から始め，道を移動しながらスポット$i$を訪問した後，再びスポット$1$に戻ってきます。 行きと帰りとで経路が異なっていてもよいです。
　ある日，$N$人のツーリストがumg toursを利用しに来ました。ツーリスト$i$は，ツアー$i$に参加します。しかしツーリストたちはVIPなので，彼らは各ツアーの途中に1回だけ，ツーリストチケットを使うことで，好きな道の移動距離を$0$にすることができます。ツアーを通して ある道の距離を$0$にできるわけではないことに注意してください。
　すべての$i\ (1\le i \le N)$について，ツーリスト$i$の最短の移動距離を求めてください。

注意

　入出力が多いため，時間制限に注意して下さい。Python使いの人はPyPy3で提出してください。PyPy3ではACを確認しています。

入力

$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$
$i\neq j$のとき$(a_i,b_i)\neq (a_j,b_j)$かつ$(a_i,b_i)\neq (b_j,a_j)$
与えらえるグラフは連結である。
与えられる入力はすべて整数である。

出力

$N$行出力してください。$i$行目には，ツーリスト$i$の最短の移動距離を出力してください。最後に改行してください。

サンプル

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