TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1107
  • 题目
  • P1107达喀尔拉力赛
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    何老板在今年的达喀尔汽车拉力赛中表现出色。现在还剩下最后一站的比赛,地图上总共有n(不超过500)个城市,最后一站的起点是1号城市,终点是n号城市。这些城市间有m(不超过10000)条道路相连接。何老板估计:因为是最后一站,所以选手们一定会选最近的道路行驶,所以这些道路上一定非常容易堵车。所以何老板决定选从起点到终点的第二短的道路行驶。问:第二短的道路是多长?

    何老板选择的第二短的路径中,可以包含任何一条在最短路中出现的道路,并且,一条路可以重复走多次。当然咯,第二短路的长度必须严格大于最短路(可能有多条)的长度,但它的长度必须不大于所有除最短路外的路径的长度。

    输入格式

    第1行: 两个整数,n和m,用空格隔开

    第2..m+1行: 每行包含三个用空格隔开的整数A、B和D,表示存在一条长度为
    D(1 <= D <= 5000)的路连接城市A和城市B

    输出格式

    1行: 输出一个整数,即城市1到城市N的第二短路的长度

    样例输入

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

    样例输出

    450


    来源  Usaco2006 Nov