WALK

Who doesn't love walks?

The map of Shumen is a set of $N$ crossroads numbered from 1 to $N$, joined by $M$ bidirectional streets numbered from 1 to $M$. Each street joins two different crossroads, and no two crossroads are joined by more than one street. Any crossroad can be reached from any other by following the streets.

Kyusho and his dog Bobby went on a night walk the night before yesterday's party. They traversed every one of the $M$ streets at least once. Bobby is exceptionally intelligent but has trouble remembering the order of the streets, so his memory is chaotic and sometimes contradictory. For example, the dog may remember that some street was traversed at moment 10 while no street is remembered at moment 9. Formally, Bobby remembers that the $i$-th street, between crossroads $a_i$ and $b_i$, was traversed at moment $c_i$.

The next morning Kyusho realized that he also has trouble remembering that night, so he wants to reconstruct the walk as well as he can. He starts a new walk at his hotel, crossroad 1. Each street he traverses must have a later moment (by Bobby's memory) than the street before it, that is, $c_{next} > c_{current}$. He may pass through a crossroad more than once.

He wants the new walk to be as long as possible, and he has not decided where it should end. For each crossroad, find the longest walk that ends there and follows the rule above. The length is the number of streets passed.

The first line contains two integers $N$ and $M$, the number of crossroads and the number of streets. Each of the next $M$ lines contains three integers $a_i$, $b_i$, and $c_i$, which describe a street between crossroads $a_i$ and $b_i$ that was traversed at moment $c_i$ according to Bobby's memory.

Print $N$ integers separated by spaces: the maximal lengths of walks from crossroad 1 to crossroads $1, 2, \dots, N$. If no walk reaches a crossroad, print 0 for it.

$2 \le N \le 10^5$, $1 \le M \le 10^6$, $1 \le a_i, b_i \le N$, $a_i \ne b_i$, $1 \le c_i \le 10^9$.

The figure below shows the streets and crossroads.

The optimal walk to crossroad 3 is $1 \overset{1}{-} 5 \overset{2}{-} 6 \overset{6}{-} 2 \overset{7}{-} 8 \overset{8}{-} 5 \overset{10}{-} 3$. At crossroad 8, we cannot continue to crossroad 7, because that street has moment 5, and we arrived through a street with moment 7.