在 Kaleidostan 有 $n$ 座城市，由 $m$ 条双向道路连接。城市编号从 $1$ 到 $n$。每条道路都有一个称为“色彩度”（colorfulness）的整数。

Keanu 想要从城市 $1$ 前往城市 $n$。他希望走最短路径，即经过道路数量最少的路径。在所有最短路径中，他想要走“万花筒路径”（kaleidoscopic route），即路径上所有道路的色彩度中，最大值与最小值之差尽可能大的那条路径。请帮助 Keanu 找到这样一条路径。

输入格式

第一行包含两个整数 $n$ 和 $m$ —— 城市数量和道路数量（$2 \le n \le 10^5$；$1 \le m \le 2 \cdot 10^5$）。

接下来的 $m$ 行中，第 $i$ 行包含三个整数 $v_i, u_i$ 和 $c_i$ —— 第 $i$ 条道路连接的城市编号，以及第 $i$ 条道路的色彩度（$1 \le v_i, u_i \le n; v_i \neq u_i; 0 \le c_i \le 10^9$）。

每对城市之间最多只有一条道路相连。保证图中任意两座城市之间都是连通的。

输出格式

第一行输出一个整数 $k$ —— 所求路径包含的道路数量。

第二行输出 $k+1$ 个整数 $c_0, c_1, \dots, c_k$ —— 路径上的城市序列（$1 \le c_i \le n; c_0 = 1; c_k = n$）。

样例

输入 1

6 8
1 5 2
5 2 5
3 5 4
1 3 10
3 4 6
4 5 7
4 6 8
2 6 1

输出 1

3
1 5 4 6

说明

在样例测试中，所求路径包含 3 条道路，其路径上道路色彩度的最大值与最小值之差为 $8 - 2 = 6$。