Animal Companion in Maze

George, a pet monkey, has slipped his leash and escaped.

George is hopping around a maze-like building with many rooms. A door between two rooms leads straight into the adjacent room, not through a corridor. Some doors are one-way: they open from only one of their two sides.

George repeats picking at random a door he can open in the room he is in and moving through it into the next room. He believes that his owner is right behind him, so he never goes straight back through the door he just came through. If another door leads to the room he has just left, he may pick that door and go back.

Once the only door he can open is the one he came through, George is confined in that room and is caught there.

You know how the rooms of the building are connected by doors, but you do not know which room George is in right now.

Moving to an adjacent room through one door takes one unit of time.

Write a program that computes the longest time that can pass before George is confined in a room. Consider every room he might have started in and every choice of doors he might make.

Depending on how the rooms are organized, George may be able to keep hopping around forever without being caught.

Doors may be on the ceilings or the floors of rooms, so the connections between rooms may not be drawable as a planar graph.

The input consists of a single test case in the following format.

n m
x1 y1 w1
.
.
.
xm ym wm

The first line has two integers $n$ and $m$, the number of rooms and the number of doors ($2 \le n \le 100000$, $1 \le m \le 100000$). Each of the next $m$ lines describes one door. The $i$-th of them has three integers $x_i$, $y_i$ and $w_i$ ($1 \le x_i \le n$, $1 \le y_i \le n$, $x_i \ne y_i$, $w_i = 1$ or $w_i = 2$). Door $i$ connects rooms $x_i$ and $y_i$. If $w_i = 1$, the door is one-way from $x_i$ to $y_i$. If $w_i = 2$, it can be used in both directions. Several doors may connect the same pair of rooms.

Print the maximum number of time units after which George is confined in a room. If George can keep hopping around forever, print Infinite.