Camino más corto en un grafo

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.

5 6
1 2 2
2 5 5
2 3 4
1 4 1
4 3 3
3 5 1

5

3 2
1 2 1
2 3 1

2