1528: 最快捷的路线
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：54
Solved：22
Description
警察局接到紧急任务，一名逃犯已在 n城市被发现，此逃犯偷窃了名贵的艺术品，因此必须由城市1 的艺术鉴别家前往才能侦破案件并逮捕逃犯。为了争分夺秒，城市1的警察必须找出一条最快捷的空中航线到达城市n。
我们把城市1与城市n 之间的航空线路图简化为下图，图上每条边上标的数值表示从一地到另一地的距离值。 请你求出从城市1到城市n 的最短路线距离值。
如下图示: 最短路线距离值为8 。 其最快捷路线为 1 → 2 → 4 → 5 → 6。
Input
输入第一行为两个正整数n m。n表示顶点个数（顶点编号为 1~n），m表示边的条数。接下来m行，每行有3个数x,y,z。表示顶点x到顶点y的距离值z。
Output
输出从城市1到城市n的最短路线距离值。
Sample Input Copy
6 9
1 2 1
1 3 1
2 3 9
2 4 3
3 5 5
4 3 4
4 5 1
4 6 5
5 6 3
Sample Output Copy
8
HINT
2=<n<=20 ; 0=<g[i][j]<=1000 (没有负数)