AT_abc261_h.[ABC261Ex] Game on Graph

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

最初，棋子被放置在顶点 $v$ 上。高桥君和青木君轮流按如下规则移动棋子：

• 如果当前棋子所在的顶点没有出边，则游戏结束。
• 如果当前棋子所在的顶点有出边，则可以选择其中一条边，沿该边移动棋子。

游戏由高桥君先手。高桥君的目标是在有限步内结束游戏，并且尽量使经过的边权和最小；青木君的目标是尽量让游戏无法在有限步内结束，如果无法做到，则尽量使经过的边权和最大。
更严格地说，目标如下：
高桥君优先保证游戏能在有限步内结束，如果可以做到，则尽量使经过的边权和最小。
青木君优先保证游戏无法在有限步内结束，如果无法做到，则尽量使经过的边权和最大。
（如果棋子多次经过同一条边，则该边的权重会被多次累加。）

请判断当两人都采取最优策略时，游戏是否会在有限步内结束。如果会结束，请输出游戏过程中经过的边权和。

输入通过标准输入按以下格式给出。

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

如果两人都采取最优策略时，游戏不会在有限步内结束，则输出 INFINITY。
如果会在有限步内结束，则输出游戏过程中经过的边权和。

限制条件

• $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$
• 输入中的所有值均为整数。

样例解释 1

首先高桥君将棋子移动到顶点 $3$，然后青木君将棋子移动到顶点 $7$，游戏结束。游戏过程中经过的边权和为 $10+30=40$。

样例解释 2

游戏不会在有限步内结束。

样例解释 3

棋子的移动顺序为 $1\to 2\to 3\to 1\to 2\to 4$。

由 ChatGPT 4.1 翻译