题目描述

我们有一个有向图，有 $N$ 个顶点和 $M$ 条边。第 $i$ 条边从顶点 $A_i$ 指向顶点 $B_i$，权重为 $C_i$。

最初，在顶点 $v$ 上有一个棋子。Takahashi 和 Aoki 将进行一场游戏，他们轮流移动棋子，规则如下：

• 如果没有边指向棋子所在的顶点，则游戏结束。
• 如果有从棋子所在的顶点出发的边，则选择其中一条边，将棋子沿着该边移动。

Takahashi 先开始。Takahashi 试图最小化棋子经过的边的总权重，而 Aoki 则试图最大化它。
更具体地说，他们的目标如下。
Takahashi 将首先优先考虑以有限步数结束游戏。如果这是可能的，他会尽量减少棋子经过的边的总权重。
Aoki 将首先优先考虑阻止游戏以有限步数结束。如果这是不可能的，他会尽量增加棋子经过的边的总权重。
（如果棋子经过同一条边多次，则权重会相应地加上相同的次数。）

确定当两名玩家都采取最优策略时，游戏是否能以有限步数结束。如果结束，则找出棋子经过的边的总权重。

约束条件

• $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$

输出格式

如果当两名玩家采取最优策略时游戏不能以有限步数结束，输出 INFINITY。
如果游戏以有限步数结束，输出棋子经过的边的总权重。

示例输入 1

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

示例输出 1

40

首先，Takahashi 将棋子移动到顶点 $3$。接下来，Aoki 将棋子移动到顶点 $7$，游戏结束。
棋子经过的边的总权重为 $10+30=40$。

示例输入 2

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

示例输出 2

INFINITY

游戏不能以有限步数结束。

示例输入 3

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

示例输出 3

5

棋子将经过路径 $1 \to 2 \to 3 \to 1 \to 2 \to 4$。