Problem Description

Given $M$ sets of relations in the form $\min(X_{A_i}, X_{B_i}) = C_i$, construct an array $X$ of length $N$ such that each number in the array is between $1$ and $10^9$, and the array satisfies all the given relations.

The problem guarantees that such an array exists.

Input Format

The first line contains two integers $N$ and $M$.

The next $M$ lines each contain three integers $A_i, B_i, C_i$.

Output Format

Output a single line containing $N$ integers, representing the constructed array $X$.

Sample Input and Output

Sample Input #1

2 1
2 1 7

Sample Output #1

9 7

Sample Input #2

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

Sample Output #2

3 1 4 1 5

Sample Input #3

2 5
1 2 1
2 1 1
1 2 1
1 2 1
2 1 1

Sample Output #3

1 114514

Sample Input #4

5 1
1 2 123

Sample Output #4

123 1000000000 3 4 26311337

Notes

Sample #1 Explanation

Clearly, $\min(X_2, X_1) = \min(9, 7) = 7$, which satisfies the condition.

Sample #3 Explanation

The first constraint is $\min(X_1, X_2) = 1$, and all other conditions are effectively the same as this constraint.

Sample #4 Explanation

The only constraint is $\min(X_1, X_2) = 123$, and the other numbers can be any within the range $1$ to $10^9$.

Data Range

For $100\%$ of the data:
- $1 \leq N, M \leq 10^5$
- $1 \leq A_i, B_i \leq N$
- $A_i \neq B_i$
- $1 \leq C_i \leq 10^9$

见题面 Input 部分

见题面 Output 部分