3315: 回家
内存限制：64 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：3
解决：2
题目描述
Joe决定回家了。
Joe的家与公园之间并不是直达的，中间要经过一些道路。
值得一提的是，Joe所在的城市有n个路口，m条道路连接，公园在路口1，Joe的家在路口n。
Joe经过部分道路时要花费一些时间，这使得Joe很苦恼。
这时Joe买的云朵告诉Joe，它可以施展魔法，让其中一条道路的时间花费变成0，这让Joe喜出望外。
Joe希望能尽早的回到家，你可以告诉他施展魔法之后最少要多少时间回到家吗？
输入
第一行，n，m，意义如题目所述
第2~m+1行，每行ui,vi,ci,表示从ui走到vi需要ci的时间
输出
一行，Joe到家的最少时间
样例输入 复制
3 2
1 2 3
2 3 2样例输出 复制
2提示
样例解释：把从1到2的路置成0
数据范围：
20%的数据保证：n<=20
100%的数据保证：n<=1,000;m<=100,000;0<=ci<=10,000