시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB26201878.261%

문제

Rar the Cat has an array X of N positive integers. He is a teacher and he wants to give his students a homework based on his array. The students in his class had learnt the min function, and Rar would like to test them on this. He have already set M homework questions, and all of them are of this form:

min(Xi, Xj) = ?

Unfortunately, Rar has lost his array! Given the M homework questions, as well as the answer key, help Rar to reconstruct a possible array that matches all of his homework answers. Such an array is guaranteed to exist.

입력

Your program must read from standard input.

The first line of the input will contain 2 numbers, N and M.

The next M lines of input will contain 3 numbers, Ai, Bi, and Ci. For all i = 1, 2, ..., M, min(XAi, XBi) = Ci.

출력

Output N numbers in a single line (separated by spaces), the array X. If multiple solutions exist, all of them will be accepted. All elements of X must be between 1 and 109 (inclusive).

제한

  • 1 ≤ N, M ≤ 105
  • 1 ≤ Ai, Bi ≤ N
  • Ai ≠ Bi
  • 1 ≤ Ci ≤ 109

예제 입력 1

2 1
2 1 7

예제 출력 1

9 7

The reconstructed array satisfies the given constraints:

  • min(X2, X1) = min(7, 9) = 7

예제 입력 2

5 6
1 2 1
3 5 4
1 5 3
1 3 3
2 3 1
2 4 1

예제 출력 2

3 1 4 1 5

The reconstructed array satisfies the given constraints:

  • min(X1, X2) = min(3, 1) = 1
  • min(X3, X5) = min(4, 5) = 4
  • min(X5, X1) = min(5, 3) = 3
  • min(X1, X3) = min(3, 4) = 3
  • min(X3, X2) = min(4, 1) = 1
  • min(X4, X2) = min(1, 1) = 1

예제 입력 3

5 1
1 2 123

예제 출력 3

123 1000000000 3 4 26311337

The only condition for the array is that min(X1, X2) = 123, the rest of the array can be any value between 1 and 109.