問題
$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