MLH的一天

题目描述:

一天，体格健壮的MLH（什么鬼）又开始了马拉松的锻炼，可是有一天MLH跑得太远了，回去要很长的一段时间。他要从第1个路口走回第n个路口。他找到了你，求你帮他找到最快的路径，使他可以最快的回到家。

输入格式:

输入共m+1行，第一行包括三个数，n，m，即路口个数，路径个数。

接下来m行，每行三个整数，x，y，v，即从第x个路口到第y个路口要花v的时间(每条路是单向的)。

输出格式:

输出只有一行，即所需最短时间。

样例输入:

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

样例输出:

6

提示:

 1<=n<=1000

1<=m<=50000

时间限制: 1000ms
空间限制: 256MB

---