You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

出行计划

题目描述

一个地区有$N$个城市，编号为$1$到$N$，这些城市通过$M$条公路相连。小明在$1$号城市，他放假想去$N$号城市旅游。他现在知道他开车通过每条道路的时间$T$，但是在他出发的时候，交通广播突然响起，说是有一条道路拥堵，通过该条道路的时间要翻倍。

但是，粗心的小明竟然没有听清楚是哪一条道路堵车了！现在他想知道，在最坏情况下，他从$1$号城市出发到达$N$号城市的最短时间是多少。

输入格式

输入文件的第一行有两个正整数 $N$ 和 $M$；下面有 $M$ 行，每行有三个数正整数 $X$,$Y$,$T$，表示城市 $X$ 和城市 $Y$ 之间有一条公路，通行时间为 $T$。

输出格式

输出所求的最少时间。

样例 #1

样例输入 #1

7 8
1 2 1
2 6 8
6 5 8
5 7 5
1 7 11
2 4 2
4 3 3
3 5 4

样例输出 #1

20

提示

样例解释1：

最好路线是$1 \to 2 \to 4 \to 3 \to 5 \to 7$。

总时间为$1$ ＋ $2$ ＋ $3$ ＋ $4$ ＋ $5$ ＝ $15$，最坏的情况要多加 $5$，所以这条路在最坏情况的总时间是 $20$ ；

如果直接$1\to 7$，虽然时间只有 $11$，但是最坏情况还要加一个 $11$，总时间 $22$，反而更坏。

数据范围

对于$40\%$的数据，$N\le 100, M\le 2000$

对于另外$20\%$的数据，$W \le 200$

对于$100\%$的数据，$3 \le N \le 500, 3 \le M \le 10000，3 \le W \le 10000$