Find The Shortest Path 2
与えられた地図には、
n 個の都市と、それらの都市を結ぶ m 本の双方向道路があります。各道路には非負整数の長さ が設定されています。あなたの課題は、都市 1 から都市 n へ至る最短経路の長さを求めることです。入力
最初の行には、空白で区切られた 2 つの整数
n と m (2 ≤ n ≤ 1000, 1 ≤ m ≤ 1000) が与えられ、これは都市の数と道路の本数を示します。続く
m 行には、それぞれ空白で区切られた 3 つの整数 、、 が記載されており、これは都市 と を結ぶ道路の長さ を表します (1 ≤ ui, vi ≤ n , 1 ≤ w_i ≤ 10^9)。出力
都市
1 から都市 n までの最短経路の長さを表す整数を 1 つ出力してください。例
入力 | 出力 |
4 5
1 2 3
1 3 5
2 4 3
3 4 3
1 4 7 | 6 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB