金字塔

题目描述

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

输入输出格式

输入格式


输入文件的第一行有两个正整数 $N$($3 \le N \le 100$)和 $M$($3 \le M \le 2000$);下面有 $M$ 行,每行有三个数正整数 $U$ 、 $V$ 、 $W$,表示直接从 $U$ 室跑到 $V$ 室($V$ 室跑到 $U$ 室)需要 $W$($3 \le W \le 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

说明

样例解释 Sample Explan: 基本上有三种路线: (1)$1 \to 2 \to 3 \to 4 \to 7$。 总时间为:$10$ + $12$ + $20$ + $8$ = $50$,最坏的情况是“ $3 \to 4$ ”那一段,要多花 $20$ 秒(因为行走速度减半),所以这条路选最坏需要 $70$ 秒; (2)$1 \to 2 \to 5 \to 6 \to 4 \to 7$。 总时间为:$10$ + $10$ + $12$ + $13$ + $8$ = $53$,最坏的情况是“ $6 \to 4$ ”那一段,要多花 $13$ 秒,所以这条路选最坏需要 $66$ 秒; (3)$1 \to 7$。 总时间为:$34$ = $34$,最坏的情况是“ $1 \to 7$ ”那一段,要多花 $34$ 秒,所以这条路选最坏需要 $68$ 秒。