CF1715D.2+ doors

The Narrator has an integer array $a$ of length $n$, but he will only tell you the size $n$ and $q$ statements, each of them being three integers $i, j, x$, which means that $a_i \mid a_j = x$, where $|$ denotes the bitwise OR operation.

Find the lexicographically smallest array $a$ that satisfies all the statements.

An array $a$ is lexicographically smaller than an array $b$ of the same length if and only if the following holds:

• in the first position where $a$ and $b$ differ, the array $a$ has a smaller element than the corresponding element in $b$.

叙述者有一个长度为 $n$ 的整数数组 $a$，但他只会告诉你数组长度 $n$ 以及 $q$ 条陈述，每条陈述由三个整数 $i, j, x$ 构成，表示 $a_i \mid a_j = x$，其中 $|$ 表示按位或运算。

请找出满足所有陈述的字典序最小的数组 $a$。

当且仅当满足以下条件时，数组 $a$ 的字典序小于同长度的数组 $b$：

• 在 $a$ 与 $b$ 首次出现差异的位置上，$a$ 中对应位置的元素小于 $b$ 中对应位置的元素。

In the first line you are given with two integers $n$ and $q$ ($1 \le n \le 10^5$, $0 \le q \le 2 \cdot 10^5$).

In the next $q$ lines you are given with three integers $i$, $j$, and $x$ ($1 \le i, j \le n$, $0 \le x \lt 2^{30}$) — the statements.

It is guaranteed that all $q$ statements hold for at least one array.

第一行给出两个整数 $n$ 和 $q$（$1 \le n \le 10^5$，$0 \le q \le 2 \cdot 10^5$）。

接下来 $q$ 行，每行给出三个整数 $i$、$j$ 和 $x$（$1 \le i, j \le n$，$0 \le x \lt 2^{30}$）——这些是约束条件。

保证存在至少一个数组满足全部 $q$ 个约束条件。

On a single line print $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \lt 2^{30}$) — array $a$.

在一行中输出 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \lt 2^{30}$）—— 数组 $a$。

In the first sample, these are all the arrays satisfying the statements:

• $[0, 3, 2, 2]$,
• $[2, 1, 0, 0]$,
• $[2, 1, 0, 2]$,
• $[2, 1, 2, 0]$,
• $[2, 1, 2, 2]$,
• $[2, 3, 0, 0]$,
• $[2, 3, 0, 2]$,
• $[2, 3, 2, 0]$,
• $[2, 3, 2, 2]$.

在第一个样例中，所有满足条件的数组如下：

• $[0, 3, 2, 2]$,
• $[2, 1, 0, 0]$,
• $[2, 1, 0, 2]$,
• $[2, 1, 2, 0]$,
• $[2, 1, 2, 2]$,
• $[2, 3, 0, 0]$,
• $[2, 3, 0, 2]$,
• $[2, 3, 2, 0]$,
• $[2, 3, 2, 2]$。