配点 : $600$ 点

問題文

$N$ 頂点 $M$ 辺の有向グラフがあります。辺 $i$ は頂点 $A_i$ から $B_i$ への有向辺で、重みが $C_i$ です。

最初、頂点 $v$ に駒が置かれています。高橋君と青木君が交互に次のように駒を動かすゲームを行います。

• 駒が置かれている頂点から出る辺が存在しないとき、ゲームを終了する。
• 駒が置かれている頂点から出る辺が存在するとき、そのうちいずれかの辺を選び、選んだ辺に沿って駒を移動する。

ゲームは高橋君から始め、高橋君はゲームが終了するまでに通った辺の重みの和を小さくしようとし、青木君は大きくしようとします。 $2$ 人が目指すものはより厳密には、次の通りです。 高橋君は、ゲームを有限回の操作で終了させることを最優先し、それが可能ならば、ゲームが終了するまでに通る辺の重みの和を小さくしようとします。 青木君は、ゲームを有限回の操作で終了させないことを最優先し、それが不可能ならば、ゲームが終了するまでに通る辺の重みの和を大きくしようとします。 （駒が同じ辺を複数回通った場合は、重みはその回数だけ加算されるものとします。）

$2$ 人が最善を尽くしたときゲームが有限回の操作で終了するか判定し、終了するならば、ゲームが終了するまでに通る辺の重みの和を求めてください。

制約

• $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$
• 入力に含まれる値は全て整数

入力

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

$N$ $M$ $v$

$A_1$ $B_1$ $C_1$

$A_2$ $B_2$ $C_2$

$\vdots$

$A_M$ $B_M$ $C_M$

出力

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

7 6 1
1 2 1
1 3 10
2 4 100
2 5 102
3 6 20
3 7 30

40

まず高橋君は頂点 $3$ に駒を動かし、次に青木君が頂点 $7$ に駒を動かし、ゲームが終了します。 ゲームが終了するまでに通る辺の重みの和は $10+30=40$ になります。

3 6 3
1 2 1
2 1 2
2 3 3
3 2 4
3 1 5
1 3 6

INFINITY

有限回の操作でゲームは終了しません。

4 4 1
1 2 1
2 3 1
3 1 1
2 4 1

5

$1\to 2 \to 3 \to 1 \to 2\to 4$ と駒は動かされます。