问题描述

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

输入文件maplesword.in

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

输出文件maplesword.out

一个整数，为将所有城市连接在一起的第二短的路径的长度（保证存在）

样例输入

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

样例输出

26

数据范围

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