在某个国家有N个城市,被编号为0到n-1,城市之间由M个班次的列车连接,每个班次的列车连接两个城市并且只会走固定的线路和方向。现在王老师来到了这个国家旅游,他在城市0下飞机,想要以最快的速度赶往城市n-1参加一个活动,因此他拿到了所有列车的信息,包括列车的出发地和目的地还有单程所需的时间。忽略城市内的路程和候车的时间,王老师希望你帮忙找出一个方案使得他能够尽早的到达城市n-1.
第一行两个整数N和M。
下面M行每行3个整数,分别代表一个班次的列车的出发地A、目的地B和所需时间T。
其中A,B<N≤2×104,M≤2×105,T≤104。
输入保证城市0和城市n-1有直接或间接的列车线路连接,并且不存在出发地和目的地都相同的列车。
第一行一个整数表示所需的最短时间。
第二行按顺序输出途径的每个城市编号,包括城市0和城市n-1,每个编号之间用“->”箭头隔开。
请输入正确的证书编号
学员姓名:孙兴民
课程:Scratch Level 1
发证日期:2019.08.15