当前没有测试数据。

Ex - 图上的游戏

得分：600 分

问题描述

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

初始时，有一个棋子在顶点 $v$ 上。高桥和青木将轮流移动棋子，规则如下：

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

高桥先行动。高桥的目标是尽量减小棋子经过的边的总权重，而青木的目标是尽量增大棋子经过的边的总权重。
更具体地说，他们的目标如下。
高桥首先优先考虑在有限次行动内结束游戏。如果可能，他会尽量减小棋子经过的边的总权重。
青木首先优先考虑无法在有限次行动内结束游戏。如果这不可能，他会尽量增大棋子经过的边的总权重。
（如果棋子经过同一条边多次，则权重增加相应的次数。）

确定当两个玩家都采取最优策略时游戏是否会在有限次行动内结束。如果结束，找出棋子经过的边的总权重。

约束条件

• $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)=(A_j,B_j)$。
• 没有自环。即，不成立 $A_i=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。
如果游戏能在有限次行动内结束，输出棋子经过的边的总权重。

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