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