Kaleidoscopic Route#11142
There are cities in Kaleidostan connected with bidirectional roads. The cities are numbered from to . Each road has an integer called colorfulness.
Keanu wants to travel from city to city . 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.
The first line contains two integers and — the number of cities and the number of roads (2 \le n \le 10^5; 1 \le m \le 2 \cdot 10^5).
The -th of the following lines contains three integers v_i, u_i, and c_i — the indices of the cities connected by the -th road, and the colorfulness of the -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.
In the first line, print a single integer — 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).
Example 1
In the example test, the required route consists of roads, and the difference between the maximum and the minimum colorfulnesses of its roads is 8-2=6.