Shortest Path

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

Input

N ≤ 1000, the number of vertices.
M ≤ 10000, 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.

Output

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

```3 3
1 2 1
2 3 2
1 3 5```

Sample Output

`3`

Take the path 1-2-3.

Point Value: 10 (partial)
Time Limit: 1.00s
Memory Limit: 32M

Problem Types: [Show]

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

• (0/0)
I've used both the bellman ford and spfa algorithms? They should handle negative edge weights...

• (0/0)
I've tried multiple algorithms, but I keep getting the last test case incorrect. What am I missing?

• (0/0)
 Bonus: one case will have edges with negative lengths.

• (0/0)
My code worked fine on windows cmd but I'm getting RE for all test cases?
Are N and M on the same line separated by a space or on different lines?

• (0/0)
N and M will be on the same line.

``Traceback (most recent call last):   File "a.out", line 19, in <module>     graph[int(a[0])].append(weight) KeyError: 3``

• (0/0)
For example:
3 3
1 2 1
2 1 -2
1 3 5

• (0/0)
AFAIK there are no such cases in the actual test data