En este problema tu tarea es encontrar la longitud del camino más corto entre el primer y último nodo en un grafo dirigido ponderado.
Entrada
La entrada consiste en un único caso de prueba.
La primera línea contiene el número de nodos y el número de aristas, \(n\) (\(1 \leq n \leq 10^5\)) y \(m\) (\(1 \leq m \leq 5 \cdot n\)) respectivamente.
Después, aparecen \(m\) líneas, cada una con tres números, indicando el nodo de orígen, destino y el coste, respectivamente. Se garantiza que el peso de una arista nunca será mayor que 1000.
Salida
En una única línea, se debe imprimir la longitud del camino más corto entre el nodo 1 y el nodo \(n\). Si no existe ningún camino válido, se debe imprimir -1.
Ejemplos
Ejemplo 1
Entrada
5 6
1 2 2
2 5 5
2 3 4
1 4 1
4 3 3
3 5 1
Salida
5
Ejemplo 2
Entrada
3 2
1 2 1
2 3 1
Salida
2
No puedes enviar código vacío.
ID
Usuario
Lenguaje
Veredicto
Tiempo
Memoria
Fecha
Problema creado para probar el sistema de evaluación del juez en línea AlgoMania.