Find The Shortest Path 2
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.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
A single integer representing the length of the shortest path from city
1 to city n.Examples
Input | Output |
4 5
1 2 3
1 3 5
2 4 3
3 4 3
1 4 7 | 6 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB