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

Input Specification

$N\le 1000$, the number of vertices.
$M\le 10000$, the number of edges. $M$ lines, each with three integers $a$, $b$, $c$ $(-100\le c\le 1000)$ 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$.