eolymp
bolt
Try our new interface for solving problems
Problems

Kaleidoscopic Route

Kaleidoscopic Route

Time limit 2 seconds
Memory limit 512 MiB

There are n cities in Kaleidostan connected with 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 to take the shortest route — that is, the route with the smallest number of roads. Among all the shortest routes, he wants to take the kaleidoscopic one — that is, the route with the largest possible difference between the maximum and the minimum colorfulnesses of its roads. Help Keanu find such a route.

Input data

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 the colorfulness of the i-th road (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.

Output data

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).

Examples

Input example #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
Output example #1
3
1 5 4 6 

Note

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

Author Pavel Mavrin