WALK

산책을 좋아하지 않는 사람이 어디 있겠는가?

슈멘 시의 지도는 1부터 $N$까지 번호가 매겨진 $N$개의 교차로와, 1부터 $M$까지 번호가 매겨진 $M$개의 양방향 도로로 이루어진다. 각 도로는 서로 다른 두 교차로를 잇고, 두 교차로를 잇는 도로는 둘 이상이 없다. 어느 교차로에서든 도로를 따라가면 다른 모든 교차로에 도달할 수 있다.

쿄슈와 그의 개 바비는 그저께 파티가 열리기 전날 밤에 야간 산책을 했다. 둘은 $M$개의 도로를 모두 최소 한 번 이상 지났다. 바비는 매우 똑똑하지만 도로를 지난 순서를 외우는 데 약해서, 기억이 뒤죽박죽이고 가끔 서로 모순되기도 한다. 예를 들어 개는 어떤 도로를 시각 10에 지났다고 기억하면서도, 시각 9에 지난 도로는 기억하지 못할 수 있다. 정확히 말하면, 바비는 교차로 $a_i$와 $b_i$를 잇는 $i$번째 도로를 시각 $c_i$에 지났다고 기억한다.

다음 날 아침 쿄슈는 자신도 그날 밤을 잘 기억하지 못한다는 것을 깨달았다. 그래서 가능한 한 정확하게 산책 경로를 되짚고 싶어 한다. 그는 호텔이 있는 교차로 1에서 새 산책을 시작한다. 지나는 도로마다 바비의 기억에 따라 직전 도로보다 나중 시각이어야 한다. 즉 $c_{next} > c_{current}$를 만족해야 한다. 같은 교차로를 두 번 이상 지나는 것도 가능하다.

그는 새 산책을 가능한 한 길게 하고 싶어 하지만, 어느 교차로에서 끝낼지는 정하지 않았다. 각 교차로에 대해, 위 규칙을 따르며 그 교차로에서 끝나는 가장 긴 산책을 구하라. 산책의 길이는 지난 도로의 개수이다.

첫 줄에 교차로의 수 $N$과 도로의 수 $M$이 주어진다. 이어지는 $M$개의 줄에는 세 정수 $a_i$, $b_i$, $c_i$가 주어진다. 이는 교차로 $a_i$와 $b_i$를 잇는 도로를 바비의 기억에 따라 시각 $c_i$에 지났다는 뜻이다.

교차로 $1, 2, \dots, N$으로 가는 산책의 최대 길이를 공백으로 구분해 $N$개의 정수로 출력한다. 어떤 교차로에도 도달하는 산책이 없다면 그 교차로에는 0을 출력한다.

$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$.

아래 그림은 도로와 교차로를 나타낸다.

교차로 3까지의 최적 산책은 $1 \overset{1}{-} 5 \overset{2}{-} 6 \overset{6}{-} 2 \overset{7}{-} 8 \overset{8}{-} 5 \overset{10}{-} 3$이다. 교차로 8에 있을 때 교차로 7로는 갈 수 없다. 그 도로의 시각은 5인데, 직전에 시각 7인 도로를 지나 왔기 때문이다.