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 翻译