問題文

重み付き無向グラフに対する最短経路問題を解いてください。 具体的には、以下のようなグラフが与えられるとき、頂点 1 から各頂点までの最短経路長を求めてください。

• 頂点数は N 、辺数は M である
• i 番目の辺は頂点 A_i と頂点 B_i を結び、長さは C_i である

なお、以降の説明では、頂点 1 から頂点 k までの最短経路長を \operatorname{dist}[k] とします。

制約

• 2 \leq N \leq 100000
• 1 \leq M \leq \min(100000,N(N-1)/2)
• 1 \leq A_i \lt B_i \leq N\ (1\leq i\leq M)
• 1 \leq C_i \leq 10000\ (1\leq i\leq M)
• i \neq j \implies (A_i,B_i) \neq (A_j,B_j)
• 入力は全て整数

入力例 1

6 7
1 2 15
1 4 20
2 3 65
2 5 4
3 6 50
4 5 30
5 6 8

出力例 1

0
15
77
20
19
27

与えられるグラフは次のようになります。

入力例 2

15 30
10 11 23
11 13 24
5 8 22
10 15 18
12 14 15
2 10 11
4 7 15
5 7 15
7 9 8
8 12 1
5 14 1
10 14 17
10 12 11
8 10 6
7 14 28
6 9 1
1 10 19
4 5 4
9 10 21
7 10 21
4 10 29
5 10 8
4 14 8
11 12 24
10 13 13
3 10 1
5 12 24
2 15 23
6 10 18
6 15 25

出力例 2

0
30
20
31
27
37
40
25
38
19
42
26
32
28
37