시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 0 0 0 0.000%

## 문제

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.

## 입력

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.