Problem : 59 - 次短路

Problem Statistics

Solved Member: 31　　Submission: 173　　User Tried: 34

Statement:

約翰每次都要去學校，為了節省時間，他每次都走了最短的路，但每次都看到一樣的店家小姐讓他覺得生活非常的無趣，而且每次都走一樣長的距離讓他覺得他體力退步了！所以他決定要走第二短路了，為了讓他覺得生活美好，他想多看幾眼店家小姐，即使看到的人是重複的也沒關係，這意味著同一條路他可能會走兩次以上！由於約翰非常喜歡第二短的路徑，所以他會不惜用各種方法來繞路，使得第二短路的路徑長嚴格大於最短路的路徑長。
但他只是單純的想多走一些距離，又不想多走太多，因此選擇了次短路，請你幫他算出他要走多長的距離吧。
痴漢(誤)住在1，而他的學校在N。

Input:Output:

第一行有兩個數字N M，分別代表有幾個地點與道路。(1 <= N <= 5000, 1 <= M <= 100000)
接下來有M行，每行三個數字A B D，代表A B之間有一條長度為D的雙向道路。(1 <= A, B <= N, 1 <= D <= 5000)

請輸出第二短路徑長(可能有多條長度都為最短)。
若是不存在次短路請輸出0。

Sample Input:Sample Output:

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

450

Source:

USACO 2006 Nov. Gold

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	1000ms	65536kb
1-1	1000ms	65536kb	10
1-2	1000ms	65536kb
2	1000ms	65536kb	10
3	1000ms	65536kb	10
4	1000ms	65536kb	10
5	1000ms	65536kb	10
6	1000ms	65536kb	10
7	1000ms	65536kb	10
8	1000ms	65536kb	10
9	1000ms	65536kb	10
10	1000ms	65536kb	10