P2832 行路难

题目背景

小X来到了山区，领略山林之乐。在他乐以忘忧之时，他突然发现，开学迫在眉睫

题目描述

山区有n座山。山之间有m条羊肠小道，每条连接两座山，只能单向通过，并会耗费小X一定时间。

小X现在在1号山，他的目的是n号山，因为那里有火车站。

然而小X的体力是有限的。他每通过一条羊肠小道，就会变得更疲劳，导致他通过任意一条羊肠小道的时间都增加1。

输入输出格式

第一行两个数，n,m

第2行到第m+1行，每行3个数A，B，C，表示A、B之间有一条羊肠小道，可以让小X花费C的时间从A移动到B

两行 第一行一个数T，表示小X需要的最短时间

第二行若干个数，用空格隔开，表示小X的移动路线

例：1 4 2 5表示：小X从1号山开始，移动到4号山，再到2号山，最后到5号山。

输入输出样例

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

7
1 3 5 

说明

n<=10000, m<=200000

数据保证没有多条最短路径