Problem : 138 - 海綿寶寶之我要吃美味蟹堡(最短路)

Problem Statistics

Solved Member: 55　　Submission: 301　　User Tried: 56

Statement:

「喔，我好愛你，蟹堡王，
　美味蟹堡，鮮嫩多汁，油味讓我好興奮，
　價錢超貴，份量超小，牆上還粘著芥末醬。」──────蟹堡王之歌

蟹堡王位於比奇堡的市中心，大家都好喜歡吃蟹堡王的美味蟹堡。
今天派大星想要去吃蟹堡王的美味蟹堡，可是因為他太胖了，所以只要走路走太遠膝蓋就會受不了。
比奇堡有n個由道路連結而成的節點，並且有m條單向道路，這m條道路可能有不同的長度。
現在派大星在節點1，他想要選一條最短的路徑走到位於節點n的蟹堡王。
不過因為他能走的路徑長度有一定限制，請你告訴他最短的一條路徑長度是多少吧！
如果不存在這樣的路徑，請輸出-1。

Input:Output:

第一行有兩個數字n, m。(n ≦ 50000, m ≦ 300000)
接下來有m行，每一行有三個數字a, b, c (1 ≦ a,b ≦ n, 0 < c ≦10000)，代表從節點a到節點b有一條長度為c的單向道路連接。

輸出一個數字，代表派大星要到蟹堡王的最短路徑。
若不存在最短路徑，請輸出-1。

Sample Input:Sample Output:

3 4
1 2 1
2 3 1
1 3 4
1 2 2

HINT:

我愛海綿寶寶>///<

Problem Setter

bigelephant29

Testdata:

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