004 - Shortest Path2

問題

頂点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