← 返回题目列表

AtCoder · tessoku_book_bl

A64. 最短路径2

中文机器翻译题面 查看原题

配点: 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