AT_abc061_d [ABC061D] Score Attack

[problemUrl]: https://atcoder.jp/contests/abc061/tasks/abc061_d $ 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` と出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ a_1 $ $ b_1 $ $ c_1 $ $ a_2 $ $ b_2 $ $ c_2 $ $ : $ $ a_M $ $ b_M $ $ c_M $

もし、ゲーム終了時のスコアをいくらでも大きくできる場合は `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\