트램

바이트맨(Byteman)은 오래된 탈것의 사진을 모읍니다. 어느 날 창밖을 내다보던 그는 집 앞 정류장에 멈춰 선 보기 드문 옛 트램을 보았지만, 카메라를 드는 사이에 트램이 떠나 버려 사진을 놓치고 말았습니다. 그는 다음 기회는 놓치지 않으려 합니다.

바이트맨이 사는 바이트타운(Bytetown)에는 $1$번부터 $n$번까지 번호가 붙은 $n$개의 교차로가 있고, 교차로마다 트램 정류장이 하나씩 있습니다. 트램은 항상 정수 분(정각)에 도착합니다. 매 분 창밖을 확인하는 대신, 바이트맨은 트램이 처음 나타난 순간을 $0$분으로 삼아 $T$분마다 정류장을 촬영하도록 카메라를 맞추기로 했습니다.

그는 트램이 어떤 경로로 다니든 트램이 자신의 정류장으로 다시 돌아오는 모든 순간이 항상 $T$의 배수가 되게 하는, 가장 큰 주기 $T$를 원합니다. 그러면 카메라는 트램을 결코 놓치지 않습니다.

이를 일반화하여 각 교차로 $j$에 대해 값 $T_j$를 다음과 같이 정의합니다. 트램이 $0$분에 교차로 $j$에 나타난 뒤 선로를 따라 이동한다고 합시다. $T_j$는 다음 성질을 만족하는 가장 큰 정수입니다. 트램이 택할 수 있는 모든 경로에 대해, 트램이 이후 다시 교차로 $j$에 오는 모든 순간이 $T_j$의 배수이다.

트램은 갈 수 있는 한 계속 움직입니다. 나가는 선로가 없는 교차로(막다른 곳)에 이르렀을 때에만 멈추며, 그렇지 않으면 영원히 달릴 수도 있습니다. 정류장에서 머무는 시간은 무시합니다.

교차로 $j$에서 나가는 선로가 하나도 없거나, $j$에서 출발한 트램이 결코 $j$로 돌아올 수 없다면 $T_j = -1$입니다.

$1$번부터 $n$번까지 모든 교차로 $j$에 대해 $T_j$를 구하세요.

첫째 줄에 두 정수 $n$과 $m$이 공백 하나로 구분되어 주어집니다 ($1 \le n, m \le 100{,}000$). 각각 교차로의 수와 선로의 수입니다. 교차로는 $1$번부터 $n$번까지 번호가 매겨져 있습니다.

이어지는 $m$개의 줄에는 각각 세 정수 $a_i$, $b_i$, $c_i$가 공백으로 구분되어 주어집니다 ($1 \le a_i, b_i \le n$, $1 \le c_i \le 10{,}000$). 이는 트램이 교차로 $a_i$에서 교차로 $b_i$로 $c_i$분 만에 이동할 수 있는 일방통행 선로를 뜻합니다.

한 쌍의 교차로 사이에 양방향 선로가 모두 있을 수 있고, $a_i = b_i$인 경우(한 교차로에서 자기 자신으로 도는 순환 선로)도 가능합니다. 임의의 한 방향에 대해 두 교차로 사이의 선로는 최대 하나입니다.

정류장에서 머무는 시간은 무시하며, 트램은 갈 수 있는 한(막다른 곳에 이를 때까지, 그렇지 않으면 영원히) 계속 이동합니다.

$n$개의 정수를 각각 한 줄에 하나씩 출력합니다. $j$번째 줄에는 $T_j$를 출력합니다.

위 그림의 예에서, 교차로 $2$번을 떠난 트램은 예컨대 $8$분, $10$분, $12$분 뒤에 돌아올 수 있습니다. 따라서 카메라가 트램의 등장을 놓치지 않으려면 $2$분마다 촬영하도록 맞춰야 하므로 $T_2 = 2$입니다.