马拉松赛跑

题目内容

题目描述

R城举办了一场马拉松比赛,这场比赛共有n个检查点,编号为1到n,参赛选手需要从1号检查点出发,经过若干个检查点后抵达终点n号检查点,如果选手们在路上耗费的时间相同,那么评委会比较他们经过的检查点的序列,该序列的字典序较小的选手将会获得胜利。

现在我们知道了m条路径,每条路径都是从一个检查点到另一个检查点的单向路径,路径的信息包括了起始检查点、到达检查点以及路径长度。

为了尽可能获得比较高的名次,请你求出从1号检查点到n号检查点的最短路径,并按顺序输出该路径经过的检查点,若存在多个最短路径,则选择字典序最小的那一条。

输入描述

第一行两个整数n和m,表示检查点和路径的数量,1≤n≤10,000,1≤m≤20,000。

接下来m行每行一条路径的信息,有三个整数,分别表示路径开始和结束的检查点,以及路径长度,长度不超过10,000。

输出描述

第一行一个整数,为最短路径长度。

第二行若干个整数,为最短路径所经过的检查点编号,编号间以空格隔开。

样例输入

5 6 1 2 5 1 3 4 1 4 8 2 4 2 3 5 6 4 5 3

样例输出

10 1 2 4 5

提示

提交评测
请登录后再操作

题目描述

马拉松赛跑
1211
0
Level4
14
9
64%
证书查询 x
请输入证书编号:

请输入正确的证书编号

学员姓名:孙兴民

课程:Scratch Level 1

发证日期:2019.08.15

证书查询

该证书不存在