Second Shortest Path
You are given
n cities and m bidirectional roads connecting them. Each road has a corresponding length 1 to city n using these roads. However, he has a twist in his plan - he will choose the shortest road among all the paths that are strictly longer than the overall shortest path.In other words, your task is to help Emil determine the length of the second shortest path from city
1 to city n.Input
The first line of the input contains two integers
n and m, representing the number of cities and the number of roads, respectively.
The next m lines contain three integers Output
Output a single integer representing the length of the second shortest path from city
1 to city n.Examples
Input | Output |
6 7
1 2 3
2 3 4
3 6 5
2 6 9
1 4 3
4 5 8
5 6 2
| 13 |
Constraints
Time limit: 5.4 seconds
Memory limit: 512 MB
Output limit: 1 MB