미로 속 반려동물

반려 원숭이 조지가 목줄을 풀고 달아났다.

조지는 방이 많은 미로 같은 건물을 뛰어다니고 있다. 방과 방을 잇는 문은 복도를 거치지 않고 바로 옆 방으로 통한다. 문 중에는 양쪽 가운데 한쪽에서만 열 수 있는 일방통행 문도 있다.

조지는 지금 있는 방에서 열 수 있는 문을 무작위로 하나 골라 그 문으로 옆 방에 옮겨 가기를 되풀이한다. 쫓아오는 사람이 바로 뒤에 있다고 믿기 때문에, 방금 지나온 문으로 곧바로 되돌아가지는 않는다. 방금 떠난 방으로 이어지는 다른 문이 있으면 그 문을 골라 돌아갈 수는 있다.

들어올 때 지난 문 말고는 열 수 있는 문이 하나도 없으면 조지는 그 방에 갇히고, 거기에서 붙잡힌다.

건물의 방과 문이 어떻게 연결되어 있는지는 알지만, 조지가 지금 어느 방에 있는지는 모른다.

문 하나를 지나 옆 방으로 옮겨 가는 데 시간 1이 걸린다.

조지가 갇히기까지 걸리는 시간의 최댓값을 구하는 프로그램을 작성하시오. 조지가 처음에 있었을 수 있는 모든 방과 조지가 고를 수 있는 모든 문 선택을 함께 따져서 가장 오래 걸리는 경우를 찾아야 한다.

방과 문의 연결 상태에 따라서는 조지가 붙잡히지 않고 영원히 뛰어다닐 수도 있다.

문은 방의 천장이나 바닥에 있을 수도 있어서, 방들의 연결 관계가 평면 그래프로 그려지지 않을 수 있다.

입력은 테스트 케이스 하나로 이루어지고, 형식은 다음과 같다.

n m
x1 y1 w1
.
.
.
xm ym wm

첫 줄에 방의 수 $n$과 문의 수 $m$이 주어진다 ($2 \le n \le 100000$, $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 \ne y_i$, $w_i = 1$ 또는 $w_i = 2$). $i$번째 문은 $x_i$번 방과 $y_i$번 방을 잇는다. $w_i = 1$이면 $x_i$번 방에서 $y_i$번 방으로만 지날 수 있는 일방통행 문이고, $w_i = 2$이면 양방향으로 지날 수 있는 문이다. 같은 두 방을 잇는 문이 여러 개일 수도 있다.

조지가 방에 갇히기까지 걸리는 시간의 최댓값을 출력한다. 조지가 영원히 뛰어다닐 수 있으면 Infinite를 출력한다.