配点: 1000 点
問題文
頂点数 N、辺数 M 的加权无向图。 顶点 来自 1 的顶点 查找到 N 的具体最短路线 1 请输出一个。 计算量为 优选 O(M \log N) 。
制約
- 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 和顶点 这意味着 N 是一个串联
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N M A_1 B_1 C_1 A_2 B_2 C_2 \vdots A_M B_M C_M
出力
按以下格式回答 1 行输出。
v_1 v_2 \cdots v_k
(v_1,v_2,\ldots,v_k) 是给定图中的顶点 必须是到 1 的顶点 查找到 N 的最短路径。 正式地,(v_1,v_2,\ldots,v_k) 必须满足的条件如下。
- v_1=1,v_k=N
- 给定的图有边 (v_i,v_{i+1}) 存在 (1\leq i\lt k)
- 以上 2 满足什么样的条件 同样对于 (u_1,u_2,\ldots,u_l) ,边缘 (v_i,v_{i+1}) 的长度之和是边 小于或等于 (u_i,u_{i+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
1 2 5 6
给定图中的顶点 到 1 的顶点 查找到 N 的最短路径是:

入力例 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
1 10 15