Kaleidoscopic Route

Kaleidostan has $n$ cities connected by $m$ bidirectional roads. The cities are numbered from 1 to $n$. Each road has an integer called colorfulness.

Keanu wants to travel from city 1 to city $n$. He wants a shortest route, meaning the route with the fewest roads. Among all shortest routes, he wants the kaleidoscopic one, meaning the route with the largest possible difference between the maximum and minimum colorfulness of its roads. Help Keanu find such a route.

The first line contains two integers $n$ and $m$, the number of cities and the number of roads ($2 \le n \le 10^5$; $1 \le m \le 2 \cdot 10^5$).

The $i$-th of the following $m$ lines contains three integers $v_i$, $u_i$, and $c_i$, the indices of the cities connected by the $i$-th road and its colorfulness ($1 \le v_i, u_i \le n$; $v_i \neq u_i$; $0 \le c_i \le 10^9$).

Each pair of cities is connected by at most one road. It is guaranteed that you can travel from any city to any other city using the roads.

In the first line, print a single integer $k$, the number of roads in the required route.

In the second line, print $k+1$ integers $c_0, c_1, \ldots, c_k$, the sequence of cities on the route ($1 \le c_i \le n$; $c_0 = 1$; $c_k = n$).

In the example test, the required route consists of 3 roads, and the difference between the maximum and minimum colorfulness of its roads is $8-2=6$.