问题 25543. -- 道路障碍

25543: 道路障碍

时间限制: 1 Sec  内存限制: 128 MB
献花: 66  解决: 30
[献花][花圈]

题目描述

      贝西搬到了一个小农场,有时候,她会回来看看她的朋友们。由于路上风景不错,她不想走得太快于是贝西决定不走最短路径,而是走次短(即第二短)的路径(假定次短路径一定是存在的)。
    村里一共有R (1 ≤ R ≤ 100000)条双向道路,N (1 ≤ N ≤ 5000)个结点(从1到N编号)。
    贝西的起点是1号点,目的地(就是她朋友的家)在N号点。
    次短路径的有些边可以和最短路径重复,而且也允许存在圈,即次短路径上允许重复多次通过一些点或边。我们要求次短路径要严格大于最短路径。比如说,如果有两条不同的路径都是最短路径,那么他们都不能算是次短路径,次短路径一定要比它们长。

输入

第一行:两个用空格分开的整数:N和R
第二行到R + 1行:每一行有三个整数:A,B和D,表示一条道路连接了A点和B点,长度为D (1 ≤ D ≤ 5000)

输出

单独一行:从1号点到N号点的第二短的路径。

样例输入

4 4 
1 2 100 
2 4 200 
2 3 250 
3 4 100

样例输出

450

提示

【hint】

(最优路线:1 2 4,长度为100 + 200 =300;次优路线 1 2 3 4,长度为100 + 250 + 100 = 450)

来源

[献花][花圈]