← 返回题目列表

AtCoder · typical90_m

013. 及格(★5)

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

配点: 5 点

問題文

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
  • 每两个城市之间都可以通过几条道路进行移动
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N M
A_1 B_1 C_1
\vdots
A_M B_M C_M

出力

N 行。 列出
k (1 \leq k \leq N第) 行,请输出到城市 1 从城市出发 转至 k 经由城市 N 移动所需的最短时间(以分钟为单位)。


入力例 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