问题描述

WW在传送旅游的过程中，无意中得知了一个秘密——传说中的枫叶宝剑即将在XX城出世。WW是何许人也？他当然不会放弃任何取得宝剑的机会,而夺得宝剑的第一步就是尽快赶到XX城！不幸的是，这个秘密由于不知名的原因而被泄露了出去。一时间，前往XX城的道路上挤满了n多不知名的想要夺取宝剑的人。他们都不是笨蛋，走的都是通往猴子森林的最短的路。WW清楚，这时候通往XX城的最短的路由于太过拥挤，已不能帮助他尽快赶往XX城。因此他委托你为他找出通往XX城的第二短的路径的长度。

输入文件

第一行两个整数n（表示城镇数，WW在标号为1的城，猴子森林标号为n），m（表示公路数）。接下来m行每行三个整数x，y，z，表示城镇x与城镇y之间有一条长度为z的公路相连。

输出文件

一个整数，为第二短的路经的长度

样例输入

5 7
1 2 8
1 4 10
2 3 9
2 4 10
2 5 1
3 4 7
3 5 10

样例输出

21

数据范围

对于全部的数据，1<=n<=1000,1<=m<=500000,1<=z<=200