1925 - グラフ上の探索の練習

問題

$N$頂点$M$辺の有向グラフがあります。
このグラフの頂点には$0,1,2,...,N-1$、辺には$0,1,2,...,M-1$と番号が付けられています。
$i$番目の辺は頂点$U_i$から$V_i$へ向かう辺で、コストは$C_i$です。
頂点$0$から頂点$N-1$への経路であって、経路上の辺のコストの総和が最小になるときの、経路上の辺のコストの総和を求めてください。
ただし、2回以上通る辺が存在する場合、その都度コストは加算するものとします。

コストの総和をいくらでも小さくできる場合は"-inf"、
頂点"0"から頂点"N-1"への経路が存在しない場合は"inf"、
それ以外の場合はコストの総和の最小値を出力してください。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$
$U_1$ $V_1$ $C_1$
$U_2$ $V_2$ $C_2$
...
$U_M$ $V_M$ $C_M$

1行目に整数$N,M$が与えられる。 2行目から$M$行にかけてに整数$U_i,V_i,C_i$が与えられる。

出力

出力の最後に改行を入れること。

制約

全ての入出力ケースについて以下を満たす。

• $1 \leq N,M \leq 3000$
• $M \leq N^2-N$
• $1 \leq U_i,V_i \leq N(1 \leq i \leq M)$
• $U_i≠V_i(1 \leq i \leq M)$
• $|C| \leq 10^9$

入出力例

入力例1

4 5
0 1 10
0 2 1
2 1 1
1 3 1
2 3 10

出力例1

3

頂点を$0,2,1,3$の順に通る経路において、コストの総和が3となり、これが最小値です。

入力例2

3 1
0 1 -1000000000

出力例2

inf

入力例3

3 3
0 1 -1
1 2 -1
2 0 -1

出力例3

-inf