题目描述

$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 と出力せよ。
有限回の操作で終了するならば、ゲームが終了するまでに通る辺の重みの和を出力せよ。

题目大意

Takahashi 和 Aoki 正在一张 $n$ 个点，$m$ 条边的带权有向图上玩游戏。游戏规则如下：

• 有一颗最初在 $s$ 点的棋子。双方轮流移动这颗棋子，Takahashi 先手。
• 每一次移动都可以使棋子从边的一端移动到另一端。如果无法移动，也就是不存在出边时，游戏结束。
• 定义一局游戏的得分为棋子移动路径上的边权之和。如果经过一条边多次，边权也计算多次。

Takahashi 想要最小化游戏的得分，但 Aoki 想要最大化得分。请输出在最优策略下游戏的最终得分。特别地，如果游戏无法结束，请输出 INFINITY。

$1\le n\le 2\times 10^5,\ 0\le m\le 2\times 10^5$。有向图保证没有重边和自环，但 不保证无环。

7 6 1
1 2 1
1 3 10
2 4 100
2 5 102
3 6 20
3 7 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\ \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$ と駒は動かされます。