题目描述

给定一张带权无向图，结点编号为 $1$ 到 $n$。求从结点 $1$ 到结点 $n$ 的一条最短路径。

若不存在从 $1$ 到 $n$ 的路径，输出 -1；若有多条最短路径，输出任意一条即可。

图中可能存在自环和重边。

输入格式

第一行输入两个整数 $n,m$（$2 \le n \le 10^5$，$0 \le m \le 10^5$），分别表示结点数和边数。

接下来 $m$ 行，每行输入三个整数 $a_i,b_i,w_i$（$1 \le a_i,b_i \le n$，$1 \le w_i \le 10^6$），表示一条连接 $a_i,b_i$ 的无向边，边权为 $w_i$。

输出格式

若不存在从结点 $1$ 到结点 $n$ 的路径，输出 -1。

否则输出一条最短路径上经过的结点编号，从结点 $1$ 开始，到结点 $n$ 结束，结点之间用空格分隔。

样例

输入：

5 6
1 2 2
2 5 5
2 3 4
1 4 1
4 3 3
3 5 1

输出：

1 4 3 5