問題
頂点1から$N$の番号が付いた$N$頂点$M$辺の有向グラフがあります。
$i$($1 \leq i \leq M$)番目の辺は頂点$A_i$から頂点$B_i$を重み$C_i$で結びます。
このグラフにおいて頂点1から頂点$N$までの最短経路を求めてください。
そのような経路が存在しないか、最短経路が無限小の場合、-1を出力すること。
入力
入力は以下の形式で標準入力から与えられる。
$N$ $M$ $A_1$ $B_1$ $C_1$ $A_2$ $B_2$ $C_2$ : $A_M$ $B_M$ $C_M$
出力
出力の最後に改行を入れること。
制約
全ての入出力ケースについて以下を満たす。
- $2 \leq N \leq 3 \times 10^{3}$
- $1 \leq M \leq 10^{4}$
- $1 \leq A_i,B_i \leq N$
- $A_i \ne B_i(1 \leq i \leq N)$
- $-10^9 \leq C_i \leq 10^9$
- 入力はすべて整数
入出力例
入力例1
3 2 1 2 7 2 3 5
出力例1
12
入力例2
5 4 5 4 2 4 3 3 3 2 1 2 1 5
出力例2
-1