Find The Shortest Path 4
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 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 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.Examples
Input | Output |
4 5
1 2 3
1 3 5
2 4 3
3 4 3
1 4 7 | 3 6
1 2 4 |
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 5 MB