AT_abc261_h [ABC261Ex] Game on Graph

[problemUrl]: https://atcoder.jp/contests/abc261/tasks/abc261_h $ N $ 頂点 $ M $ 辺の有向グラフがあります。辺 $ i $ は頂点 $ A_i $ から $ B_i $ への有向辺で、重みが $ C_i $ です。 最初、頂点 $ v $ に駒が置かれています。高橋君と青木君が交互に次のように駒を動かすゲームを行います。 - 駒が置かれている頂点から出る辺が存在しないとき、ゲームを終了する。 - 駒が置かれている頂点から出る辺が存在するとき、そのうちいずれかの辺を選び、選んだ辺に沿って駒を移動する。 ゲームは高橋君から始め、高橋君はゲームが終了するまでに通った辺の重みの和を小さくしようとし、青木君は大きくしようとします。 $ 2 $ 人が目指すものはより厳密には、次の通りです。 高橋君は、ゲームを有限回の操作で終了させることを最優先し、それが可能ならば、ゲームが終了するまでに通る辺の重みの和を小さくしようとします。 青木君は、ゲームを有限回の操作で終了させないことを最優先し、それが不可能ならば、ゲームが終了するまでに通る辺の重みの和を大きくしようとします。 （駒が同じ辺を複数回通った場合は、重みはその回数だけ加算されるものとします。） $ 2 $ 人が最善を尽くしたときゲームが有限回の操作で終了するか判定し、終了するならば、ゲームが終了するまでに通る辺の重みの和を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ v $ $ A_1 $ $ B_1 $ $ C_1 $ $ A_2 $ $ B_2 $ $ C_2 $ $ \vdots $ $ A_M $ $ B_M $ $ C_M $

$ 2 $ 人が最善を尽くしたとき、ゲームが有限回の操作で終了しないならば `INFINITY` と出力せよ。 有限回の操作で終了するならば、ゲームが終了するまでに通る辺の重みの和を出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 2\times\ 10^5 $ - $ 0\ \leq\ M\ \leq\ 2\times\ 10^5 $ - $ 1\ \leq\ v\ \leq\ N $ - $ 1\ \leq\ A_i,B_i\ \leq\ N $ - 多重辺は存在しない。すなわち $ i\neq\ j $ のとき $ (A_i,B_i)\neq(A_j,B_j) $ - 自己辺は存在しない。すなわち $ A_i\neq\ B_i $ - $ 0\ \leq\ C_i\ \leq\ 10^9 $ - 入力に含まれる値は全て整数 ### Sample Explanation 1 まず高橋君は頂点 $ 3 $ に駒を動かし、次に青木君が頂点 $ 7 $ に駒を動かし、ゲームが終了します。 ゲームが終了するまでに通る辺の重みの和は $ 10+30=40 $ になります。 ### Sample Explanation 2 有限回の操作でゲームは終了しません。 ### Sample Explanation 3 $ 1\to\ 2\ \to\ 3\ \to\ 1\ \to\ 2\to\ 4 $ と駒は動かされます。