Background

Translated from NOISG2019 Prelim B.Lost Array.

This problem uses Special Judge. Any answer that satisfies the conditions will be considered correct.

Problem Description

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

It is guaranteed that such an array exists.

Input Format

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

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

Output Format

Output one line with $N$ integers, representing the array $X$ you construct.

2 1
2 1 7

9 7

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

3 1 4 1 5

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

1 114514

5 1
1 2 123

123 1000000000 3 4 26311337

Hint

Sample #1 Explanation

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

Sample #3 Explanation

The original statement did not include this sample, but it exists in the testdata.

The first constraint is $\min (X_1, X_2) = 1$. In fact, all constraints are the same as this one.

Sample #4 Explanation

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

Constraints

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

Translated by ChatGPT 5