给您一个加权无向图。顶点从 1 到 n 进行枚举。你的任务是找到顶点 1 和顶点 n 之间的最短路径。
输入
第一行包含两个整数 n 和 m (2 ≤ n ≤ 105, 0 ≤ m ≤ 105),其中 n 是顶点数,m 是边数。接下来的 m 行分别包含一条边,其形式为 ai、bi 和 wi (1 ≤ ai, bi ≤ n, 1 ≤ wi ≤ 106),其中 ai、bi 是边端点,wi 是边长度。
该图可能在一对顶点之间存在循环和多条边。
输出
如果没有路径,则写入唯一的整数-1。写出相反情况的最短路径。如果有很多解决方案,请打印其中任何一个。
示例
输入 #1
5 6 1 2 2 2 5 5 2 3 4 1 4 1 4 3 3 3 5 1
输出 #1
1 4 3 5
输入 #2
5 6 1 2 2 2 5 5 2 3 4 1 4 1 4 3 3 3 5 1
输出 #2
1 4 3 5