Given a directed graph, find the length of the shortest path from ~1~ to ~N~.

Input Specification

~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~ ~(-100 \le c \le 1\,000)~ 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.

Output Specification

The length of the shortest path from vertex ~1~ to vertex ~N~.

Sample Input

3 3
1 2 1
2 3 2
1 3 5

Sample Output

3

Take the path ~1 \to 2 \to 3~.