R城举办了一场马拉松比赛,这场比赛共有n个检查点,编号为1到n,参赛选手需要从1号检查点出发,经过若干个检查点后抵达终点n号检查点,如果选手们在路上耗费的时间相同,那么评委会比较他们经过的检查点的序列,该序列的字典序较小的选手将会获得胜利。
现在我们知道了m条路径,每条路径都是从一个检查点到另一个检查点的单向路径,路径的信息包括了起始检查点、到达检查点以及路径长度。
为了尽可能获得比较高的名次,请你求出从1号检查点到n号检查点的最短路径,并按顺序输出该路径经过的检查点,若存在多个最短路径,则选择字典序最小的那一条。
第一行两个整数n和m,表示检查点和路径的数量,1≤n≤10,000,1≤m≤20,000。
接下来m行每行一条路径的信息,有三个整数,分别表示路径开始和结束的检查点,以及路径长度,长度不超过10,000。
第一行一个整数,为最短路径长度。
第二行若干个整数,为最短路径所经过的检查点编号,编号间以空格隔开。
请输入正确的证书编号
学员姓名:孙兴民
课程:Scratch Level 1
发证日期:2019.08.15