You are given a map consisting of n cities and m bidirectional roads connecting these cities. Each road has a non-negative integer length denoted by . Your task is to find the shortest path between city 1 and city n.
π‘
Note that in this task you have to find both, the length of the shortest path and the path itself.
Input
The first line contains two space-separated integers, n and m (), representing the number of cities and the number of roads, respectively.
The next m lines each contain three space-separated integers , , and , representing a road between cities and with length ().
Output
Two integers, k and l, separated by a space. Here, k represents the number of cities in the shortest path, and l represents the length of the shortest path.
On the next line output k space-separated integers representing the cities in the shortest path.
In case there are multiple shortest paths, you can output any of them. Also, note that there is no need to minimize the number k.