題目 2407:
信息學奧賽一本通T1498-Roadblocks
時間限制: 2s
內存限制: 192MB 提交: 49 解決: 21
題目描述
原題來自：USACO 2006 Nov. Gold
貝茜把家搬到了一個小農場，但她常常回到 FJ 的農場去拜訪她的朋友。貝茜很喜歡路邊的風景，不想那么快地結束她的旅途，于是她每次回農場，都會選擇第二短的路徑，而不象我們所習慣的那樣，選擇最短路。
貝茜所在的鄉(xiāng)村有 R(1≤R≤105) 條雙向道路，每條路都連接了所有的 N(1≤N≤5000) 個農場中的某兩個。貝茜居住在農場 1，她的朋友們居住在農場 N（即貝茜每次旅行的目的地）。
貝茜選擇的第二短的路徑中，可以包含任何一條在最短路中出現的道路，并且一條路可以重復走多次。當然第二短路的長度必須嚴格大于最短路（可能有多條）的長度，但它的長度必須不大于所有除最短路外的路徑的長度。
輸入格式
第 1 行為兩個整數，N 和 R，用空格隔開；
第 2…R+1 行：每行包含三個用空格隔開的整數 A、B 和 D，表示存在一條長度為 D(1≤D≤5000) 的路連接農場 A 和農場 B。
輸出格式
輸出僅一個整數，表示從農場 1 到農場 N 的第二短路的長度。
樣例輸入
4 4
1 2 100
2 4 200
2 3 250
3 4 100
提示
最短路：1→2→4（長度為 100+200=300）
第二短路：1→2→3→4（長度為 100+250+100=450）