题目描述

有一个有向图，求由 $1$ 点到 $n$ 点的最短路径。

并且打印出具体的最短路，如果有多条最短路，优先选择编号较小的节点。

输入格式

第一行两个整数，$n,m$

n是顶点数，m是边数

接下来m行，x，y，w

表示x和y之间有一条权值为w的边

保证输入时 x 按照升序给出

如果 x 相同的情况下 按照y的升序给出

保证 1 能够到达 n

输出格式

输出共2行

第01行: 一个数，表示 $1$ 到 $n$ 的最短路

第02行: 输出1到n的最短路径序列，每个数字用空格隔开。

样例

intput

7 11 5 4
1 4 3
2 4 2
2 4 3
3 4 3
5 6 3
5 7 5
6 1 1
6 3 4
7 2 2
7 2 1
7 3 3

output

7
5 6 1 4

数据范围与提示

$1 \le n \le 2500$

$1 \le m \le 6200$