問題文

AGC 王国には N 個の街があり、それぞれ 1, 2, \cdots, N の番号がついています。また、街と街を結ぶ M 本の道路があります。i 番目の道路は街 A_i と B_i を双方向に結んでおり、通るのに C_i 分かかります。

k = 1, 2, \cdots, N それぞれについて、街 1 から街 k を経由して街 N まで移動するときにかかる時間の最小値を求めてください。

制約

• 2 \leq N \leq 100000
• 1 \leq M \leq \min\left(100000, \frac{N(N-1)}{2}\right)
• 1 \leq A_i < B_i \leq N
• (A_i, B_i) \neq (A_j, B_j) (1 \leq i < j \leq M)
• 1 \leq C_i \leq 10000
• どの街の間もいくつかの道路を通って移動が可能である
• 入力はすべて整数

入力例 1

7 9
1 2 2
1 3 3
2 5 2
3 4 1
3 5 4
4 7 5
5 6 1
5 7 6
6 7 3

出力例 1

8
8
9
9
8
8
8

例えば k = 3 のときは、以下のような経路を通るのが最適です。このときかかる時間は 9 分であるので、3 行目には 9 を出力します。

入力例 2

4 3
1 2 1
2 3 10
3 4 100

出力例 2

111
111
111
111

入力例 3

4 3
1 2 314
1 3 159
1 4 265

出力例 3

265
893
583
265