問題
$N$ 頂点 $M$ 辺の重み付き無向グラフが与えられる。このグラフ上を頂点 $1$ から頂点 $N$ まで移動することができるかどうか判定し、可能な場合はその最短距離の値を答えよ。
入力
入力は以下の形式で標準入力から与えられる。
$N$ $M$ $a_1$ $b_1$ $d_1$ $a_2$ $b_2$ $d_2$ ... $a_M$ $b_M$ $d_M$
1行目にグラフの頂点数 $N$ と辺の数 $M$ が半角スペース区切りで与えられる。
次の $M$ 行では、頂点 $a_i$ と頂点 $b_i$ との間に距離 $d_i$ の辺 $i$ ($1 \leq i \leq M$) が結ばれていることを示している。
出力
頂点 $1$ から頂点 $N$ までの最短距離を出力せよ。ただし、頂点 $1$ から頂点 $N$ まで辿り着くことができない場合は $-1$ を出力せよ。出力の最後に改行を入れること。
制約
全ての入出力ケースについて以下を満たす。
- $2 \leq N \leq 10^{3},1 \leq M \leq N(N-1)/2 $
- $1 \leq d_i \leq 10^9 (1 \leq i \leq M)$
- グラフは多重辺、自己ループを含まない。
入出力例
入力例1
5 5 1 2 3 1 3 2 2 5 8 3 4 2 4 5 2
出力例1
6
入力例2
4 2 1 2 100 2 3 100
出力例2
-1
頂点 $1$ から頂点 $4$ まで辿り着くことはできない。