問題文

$N$ 頂点 $M$ 辺の重み付き有向グラフがあります。
$i(1≦i≦M)$ 番目の辺は 頂点 $a_i$ から 頂点 $b_i$ を重み $c_i$ で結びます。
このグラフと駒を利用して、次の1人ゲームを行います。

最初、駒を頂点 $1$ に置いて、プレイヤーのスコアを $0$ とします。
プレイヤーは、次の条件で駒を繰り返し移動させることができます。

• 頂点 $a_i$ に駒があるとき、$i$ 番目の辺を利用して頂点 $b_i$ に移動する。移動後にプレイヤーのスコアが $c_i$ 加算される。

頂点 $N$ に駒があるときのみ、ゲームを終了できます。
なお、与えられる有向グラフの上で頂点 $1$ から頂点 $N$ に移動できることは保障されています。

プレイヤーがゲーム終了時のスコアを出来るだけ大きくするような行動を取ったとき、ゲーム終了時のスコアはいくつになるでしょうか?
ゲーム終了時のスコアをいくらでも大きくできる場合は inf と出力してください。

制約

• $2≦N≦1000$
• $1≦M≦min(N(N-1),2000)$
• $1≦a_i,b_i≦N (1≦i≦M)$
• $a_i≠b_i (1≦i≦M)$
• $a_i≠a_j$ または $b_i≠b_j (1≦i<j≦M)$
• $\-10^9≦c_i≦10^9 (1≦i≦M)$
• $c_i$ は整数である。
• 与えられるグラフには、頂点 $1$ から頂点 $N$ への経路が存在する。

入力

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

$N$ $M$
$a_1$ $b_1$ $c_1$
$a_2$ $b_2$ $c_2$ $:$
$a_M$ $b_M$ $c_M$

出力

もし、ゲーム終了時のスコアをいくらでも大きくできる場合は inf、そうでない場合はゲーム終了時のスコアの最大値を出力せよ。

入力例 1

3 3
1 2 4
2 3 3
1 3 5

出力例 1

7

駒を頂点 $N=3$ に移動できる経路は以下の $2$ 通りです。

• 頂点 $1$ → 頂点 $2$ → 頂点 $3$ : スコア $4+3=7$
• 頂点 $1$ → 頂点 $3$ : スコア $5$

したがって、ゲーム終了時のスコアの最大値は $7$ となります。

入力例 2

2 2
1 2 1
2 1 1

出力例 2

inf

頂点 $1$ → 頂点 $2$ → 頂点 $1$ → 頂点 $2$ … と移動することで、ゲーム終了時のスコアをいくらでも増やせます。

入力例 3

6 5
1 2 -1000000000
2 3 -1000000000
3 4 -1000000000
4 5 -1000000000
5 6 -1000000000

出力例 3

-5000000000