图上的博弈

题目描述

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

最初,棋子放在顶点 $v$ 上。Takahashi 和 Aoki 将交替移动棋子进行游戏,规则如下:

如果棋子所在的顶点没有出边,则游戏结束。

如果棋子所在的顶点有出边,则选择其中一条边,将棋子沿该边移动。

Takahashi 先手。Takahashi 试图最小化棋子经过的所有边的总权重,Aoki 试图最大化它。

更正式地,他们的目标如下。

Takahashi 最优先考虑让游戏在有限步内结束。如果可行,他会尝试最小化棋子经过的所有边的总权重。

Aoki 最优先考虑阻止游戏在有限步内结束。如果不可行,他会尝试最大化棋子经过的所有边的总权重。

(如果棋子多次经过同一条边,权重按经过次数累加。)

当双方都采取最优策略时,判断游戏是否会在有限步内结束。如果会结束,求出棋子经过的所有边的总权重。

输入格式

输入按以下格式从标准输入给出：

$N$ $M$ $v$
$A_1$ $B_1$ $C_1$
$A_2$ $B_2$ $C_2$
$\vdots$
$A_M$ $B_M$ $C_M$

输出格式

如果双方都采取最优策略时游戏不会在有限步内结束,则输出 INFINITY。

如果游戏会在有限步内结束,则输出棋子经过的所有边的总权重。

样例

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

40

首先,Takahashi 将棋子移动到顶点 $3$。接下来,Aoki 将棋子移动到顶点 $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$ 移动。

数据范围

• $1 \le N \le 2 \times 10^5$
• $0 \le M \le 2 \times 10^5$
• $1 \le v \le N$
• $1 \le A_i,B_i \le N$
• 没有重边。即,当 $i \neq j$ 时,$(A_i,B_i)\neq(A_j,B_j)$。
• 没有自环。即,$A_i\neq B_i$。
• $0 \le C_i \le 10^9$
• 输入均为整数