Find The Shortest Path 1 (最短経路を求める 1)
与えられたのは、n 個の都市と、それらの都市を結ぶ m 本の双方向道路からなる地図です。各道路の長さはゼロ以上の整数 w_i で表されます。目的は、city 1 から city n までの最短経路の長さを見つけることです。
入力
最初の行には、n と m (2 ≤ n ≤ 10^5, 1 ≤ m ≤ 10^5) がスペース区切りで与えられ、これは都市の数と道路の数を表します。
続く m 行には、ui、vi、wi という 3 つの整数がスペース区切りで与えられます。各行は、cities ui と vi を結ぶ道路があり、その長さが wi であることを示しています (1 ≤ ui, vi ≤ n, 1 ≤ w_i ≤ 10)。
出力
プログラムは、city 1 から city n までの最短経路の長さを出力してください。
例
Input | Output |
4 5
1 2 3
1 3 5
2 4 3
3 4 3
1 4 7 | 6 |
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB