你的宠物猴子 George 逃跑了，挣脱了皮带！

George 在一栋像迷宫一样的建筑里四处跳跃，建筑里有很多房间。房间的门（如果有的话）直接通向相邻的房间，而不是通过走廊。然而，有些门是单向的：它们只能从其中一侧打开。

他会随机选择一扇他能打开的门，并穿过它进入另一个房间。你正在追赶他，但他动作太快，你很难抓住他。他从不立即通过刚才进来的那扇门回到刚才离开的房间，因为他认为你在他身后。然而，如果有其他门通向他刚刚离开的房间，他可能会选择那扇门并折返回去。如果除了他刚才进来的那扇门之外，他无法打开任何其他门，那么最终你就能在那里抓住他。

你知道建筑里的房间是如何通过门连接的，但你不知道 George 目前在哪个房间。

George 通过一扇门移动到相邻房间需要一个单位的时间。

编写一个程序，计算 George 被困在一个房间之前可能需要多长时间。你需要考虑 George 最初可能在的所有房间，以及他选择通过门的所有可能性，找出最长的时间。

请注意，根据房间的组织方式，George 可能有永远四处跳跃而不被抓住的可能性。

门可能位于房间的天花板或地板上；房间的连接方式可能无法绘制成平面图。

输入格式

输入包含单个测试用例，格式如下：

$n$ $m$ $x_1$ $y_1$ $w_1$ $\vdots$ $x_m$ $y_m$ $w_m$

第一行包含两个整数 $n$ ($2 \le n \le 100000$) 和 $m$ ($1 \le m \le 100000$)，分别表示房间数和门的数量。接下来的 $m$ 行包含门的信息。其中第 $i$ 行包含三个整数 $x_i, y_i$ 和 $w_i$ ($1 \le x_i \le n, 1 \le y_i \le n, x_i \neq y_i, w_i = 1$ 或 $2$)，表示第 $i$ 扇门连接编号为 $x_i$ 和 $y_i$ 的两个房间。如果 $w_i = 1$，则该门是从 $x_i$ 到 $y_i$ 的单向门；如果 $w_i = 2$，则该门是双向门。

输出格式

输出 George 被困在房间之前所需的最大时间单位数。如果 George 有可能永远四处跳跃而不被抓住，则输出 “Infinite”。

样例

样例输入 1

2 1
1 2 2

样例输出 1

1

样例输入 2

2 2
1 2 1
2 1 1

样例输出 2

Infinite

样例输入 3

6 7
1 3 2
3 2 1
3 5 1
3 6 2
4 3 1
4 6 1
5 2 1

样例输出 3

4

样例输入 4

3 2
1 3 1
1 3 1

样例输出 4

1