You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题面描述

Arisa 和 Kasumi 在玩游戏。

她们画了一个 $N$ 个点，$M$ 条边的无向图，第 $i$ 条边从点 $A_i$ 出发，到点 $B_i$，边权为 $C_i$。

初始时，有一个棋子在点 $v$。Arisa 和 Kasumi 轮流进行（Arisa 先手）以下操作：

• 如果没有边从棋子所在的点出发，则游戏结束；
• 如果有边，则选择任意一条边，将棋子顺着这条边移动。

Arisa 优先让游戏在有限次内结束。如果可能，则最小化棋子经过边的边权之和；

Kasumi 优先让游戏不在有限次内结束。如果不行，则最大化棋子经过边的边权之和。

如果棋子经过了多次同一条边，边权之和也多次累加。

她们想知道这个游戏会不会在有限次内结束。如果会，她们想知道棋子经过边的边权之和是多少。

输入格式

第一行三个整数 $N,M,v$；

第二至 $M+1$ 行中，第 $i + 1$ 行三个整数 $A_i,B_i,C_i$。

输出格式

如果游戏不会在有限次内结束，输出 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

样例 1 解释

Arisa 将棋子移到点 $3$，Kasumi 将棋子移到点 $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

样例 3 解释

棋子的路线为：$1 \to 2 \to 3 \to 1 \to 2 \to 4$。

数据范围

• $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$
• $0 \leq C_i \leq 10^9$
• 保证图中无重边、无自环