Segunda Ruta Más Corta
Se te proporcionan
n ciudades y m caminos bidireccionales que las conectan. Cada camino tiene una longitud asociada . Emil, un viajero intrépido, quiere ir desde la ciudad 1 hasta la ciudad n utilizando estos caminos. Sin embargo, tiene un giro particular en su plan: elegirá la ruta más corta dentro de todas las que sean estrictamente más largas que la ruta más corta general.En otras palabras, tu tarea es ayudar a Emil a determinar la longitud de la segunda ruta más corta desde la ciudad
1 hasta la ciudad n.Entrada
La primera línea de la entrada contiene dos números enteros
n y m, que indican la cantidad de ciudades y la cantidad de caminos, respectivamente.
Las siguientes m líneas contienen tres enteros , y , señalando que existe un camino bidireccional entre la ciudad y la ciudad con longitud .Salida
Imprime un único entero que represente la longitud de la segunda ruta más corta desde la ciudad
1 hasta la ciudad n.Ejemplos
Entrada | Salida |
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