Encuentra la ruta más corta 3
Tienes un mapa compuesto por
n ciudades y m carreteras bidireccionales que conectan estas ciudades. Cada carretera tiene una longitud entera no negativa, denotada por . Tu objetivo es determinar la longitud del camino más corto entre la ciudad 1 y la ciudad n.Entrada
La primera línea contiene dos enteros separados por un espacio,
n y m (), que representan la cantidad de ciudades y la cantidad de carreteras, respectivamente.Las siguientes
m líneas contienen cada una tres enteros separados por espacio: , , y , que describen una carretera entre las ciudades y con longitud ().Salida
Un único entero que representa la longitud del camino más corto entre la ciudad
1 y la ciudad n.Ejemplos
Entrada | Salida |
4 5
1 2 3
1 3 5
2 4 3
3 4 3
1 4 7 | 6 |
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB