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.
The first line contains two integers n and m — the number of cities and the number of roads (2≤n≤105; 1≤m≤2⋅105).
The i-th of the following m lines contains three integers vi, ui, and ci — the indices of the cities connected by the i-th road, and the colorfulness of the i-th road (1≤vi,ui≤n; vi=ui; 0≤ci≤109).
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 c0,c1,…,ck — the sequence of cities on the route (1≤ci≤n; c0=1; ck=n).
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.