题目背景

小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 \le 10^4$，$m \le 2\times 10^5$。

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