Tram

Byteman collects photos of old vehicles. One day, looking out of his window, he saw a rare old tram stopped at the stop right in front of his house, but it left before he could pick up his camera, so he missed the shot. He wants to be ready next time.

Byteman lives in Bytetown, which has $n$ junctions numbered from $1$ to $n$, with one tram stop at each junction. Trams always arrive at whole minutes. Instead of checking the stop every single minute, Byteman decides to set his camera to photograph the stop every $T$ minutes, taking the moment the tram first appears as minute $0$.

He wants the largest period $T$ such that, no matter which route the tram takes, every moment it returns to his stop is a multiple of $T$. That way the camera never misses the tram.

Generalizing, for each junction $j$ define the value $T_j$ as follows. Suppose the tram appears at junction $j$ at minute $0$ and then travels along the tracks. $T_j$ is the largest integer such that, over every route the tram may take, every later moment at which the tram is again at junction $j$ is a multiple of $T_j$.

The tram keeps moving as long as it can. It stops only when it reaches a junction with no outgoing track (a dead end); otherwise it may run forever. The time spent waiting at a stop is negligible.

If junction $j$ has no outgoing track, or if a tram leaving junction $j$ can never return to $j$, then $T_j = -1$.

For every junction $j$ from $1$ to $n$, compute $T_j$.

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 100{,}000$), separated by a single space: the number of junctions and the number of tracks. Junctions are numbered from $1$ to $n$.

Each of the next $m$ lines contains three integers $a_i$, $b_i$, $c_i$ ($1 \le a_i, b_i \le n$, $1 \le c_i \le 10{,}000$), separated by single spaces. Each such track is one-way and lets a tram travel from junction $a_i$ to junction $b_i$ in $c_i$ minutes.

Both directions between a pair of junctions may exist, and $a_i = b_i$ is allowed (a loop at a single junction). For any given direction there is at most one track between a pair of junctions.

The time a tram spends waiting at a stop is negligible, and the tram travels as long as it can (until it reaches a dead end, or forever if it never does).

Print $n$ integers, each on its own line. The $j$-th line must contain $T_j$.

In the example above, a tram leaving junction $2$ can return after, for instance, $8$, $10$, or $12$ minutes. So, for the camera not to miss any appearance of the tram, it must be set to take a photo every two minutes, giving $T_2 = 2$.