## 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.### Sample Input

3 3 1 2 1 2 3 2 1 3 5

### Sample Output

3

Take the path 1-2-3.

All Submissions

Best Solutions

**Point Value:** 10 (partial)

**Time Limit:** 1.00s

**Memory Limit:** 32M

**Added:** Mar 04, 2009

**Problem Types:**[Show]

**Languages Allowed:**

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

## Comments (Search)

Bon Oct 13, 2013 - 3:06:04 am UTC Infinitely short paths.3 3

1 2 1

2 1 -2

1 3 5

bbi5291on Oct 13, 2013 - 3:33:54 am UTC Re: Infinitely short paths.