Problem1678--最简单的最短路问题

1678: 最简单的最短路问题

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Solved: 2Submit: 15Statistics

Description

给出一个图，起始点是1，结束点是N，边是双向的。求点1到点N的最短距离。哈哈，这就是标准的最短路径问题。

Input

测试数据第一行为一个整数t，表示有t组测试数据。
每组测试数据的第一行为两个整数N（1≤N≤200）和M（0≤M≤10000）。N表示图中点的数目，M表示图中边的数目。
下来M行，每行三个整数x，y，c表示点x到点y之间存在一条边长度为c。（x≠y,1≤c≤10000）

Output

每组测试数据输出一行，一个整数，即为点1到点N的最短距离。 如果点1和点N不联通则输出-1。

Sample Input Copy 

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

Sample Output Copy 

3
2

Source/Category

最短路 图论 
SubmitWeb Board