该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

huhe是一位城市马拉松爱好者，可是有一天他跑得太远了，回去要很长的一段时间。他要从第1个路口跑回第n个路口。他找到了你，求你帮他找到最快的路径，使他可以最快的回到家。

Format

Input

输入共m+1行，第一行包括三个数，n，m，即路口个数，路径个数。 接下来m行，每行三个整数，x，y，v，即从第x个路口到第y个路口要花v的时间(每条路是单向的)。

Output

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

Samples

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

6

Tips

对于100%的数据，2<=n<=10000，1<=m<=20000,0<=v<=100,000；