← 返回题目列表

Codeforces · 20/C

C. 迪杰斯特拉?

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

给您一个加权无向图。顶点从 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