配点: 1000 点
問題文
解决带权无向图的最短路径问题。 具体来说,当给出下图时,顶点 求从 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)
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N M A_1 B_1 C_1 A_2 B_2 C_2 \vdots A_M B_M C_M
出力
k 行是 代表 \operatorname{dist}[k] 的值。 然而,顶点 如果您无法移至 k ,请改为 -1 。
入力例 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