Given a directed graph, find the length of the shortest path from ~1~ to ~N~.
~N \le 1\,000~, the number of vertices.
~M \le 10\,000~, the number of edges.
~M~ lines, each with three integers ~a~, ~b~, ~c~ indicating a directed edge from ~a~ to ~b~ of length ~c~.
Bonus: one case will have edges with negative lengths.
A shortest path will always exist.
The length of the shortest path from vertex ~1~ to vertex ~N~.
3 3 1 2 1 2 3 2 1 3 5
Take the path ~1-2-3~.