题目描述

有一盗墓者潜入一金字塔盗宝。当她打开一个宝箱的时候，突然冒出一阵烟，她迅速意识到形势不妙，三十六计走为上计……由于她盗得了金字塔的地图，所以她希望能找出最佳逃跑路线。地图上标有N个室，她现在就在1室，金字塔的出口在N室。她知道一个秘密：那阵烟会让她在直接连接某两个室之间的通道内的行走速度减半。她希望找出一条逃跑路线，使得在最坏的情况下所用的时间最少。

输入格式：

输入文件的第一行有两个正整数N（3≤N≤100）和M（3≤M≤2000）；下面有M行，每行有三个数正整数U、V、W，表示直接从U室跑到V室（V室跑到U室）需要W（3≤W≤255）秒。

输出格式：

输出所求的最少时间（单位为秒）。

输入样例#1：

7 8
1 2 10
2 3 12
3 4 20
4 7 8
1 7 34
2 5 10
5 6 12
6 4 13

输出样例#1：

66

样例解释：

基本上有三种路线：
（1）1→2→3→4→7。
总时间为：10 ＋ 12 ＋ 20 ＋ 8 ＝ 50，最坏的情况是“ 3→4 ”那一段，要多花 20 秒（因为行走速度减半），所以这条路选最坏需要 70 秒；
（2）1→2→5→6→4→7。
总时间为：
10 ＋ 10 ＋ 12 ＋ 13 ＋ 8 ＝ 53，最坏的情况是“ 6→4 ”那一段，要多花 13 秒，所以这条路选最坏需要 66 秒；
（3）1→7。
总时间为：34 ＝ 34，最坏的情况是“ 1→7 ”那一段，要多花 34 秒，所以这条路选最坏需要 68 秒。