Problem1616--图-Floyd最短路

1616: 图-Floyd最短路

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 261  Solved: 96
[Status] [Submit] [Creator:]

Description

输入一个有向图,包含n(n<=10^2)个节点,m(m<=10^3)条有向边,所有边的长度w范围为 0<w<=100,题目确保没有自环,但可能有重边。
输出从1号节点到n号节点的最短距离。

Input

第一行n,m,有n个点,m条边,
以下m行每行3个正整数,表示每条边连接的起点,终点和长度。

Output

1号节点到n号节点的最短路径,若无法到达输出-1

Sample Input Copy

5 4
1 2 10
2 3 10
3 4 10
4 5 10

Sample Output Copy

40

Source/Category

 提高A