Graph Contest 3 P2 - Shortest Path

Description

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.
• The next $M$ lines each contain three integers $a$, $b$, and $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

Print a single integer — the length of the shortest path from vertex $1$ to vertex $N$.

---

Sample Input 1

Sample Output 1

Explanation:

Take the path $1 \rightarrow 2 \rightarrow 3$.