题目描述

"尽管有过分歧和碰撞，但我们一起找到了闪耀，我们的邂逅肯定有其意义。所以， 我在舞台上等你。"

有 $\red{n }$位舞台少女，编号从 $\red{1 }$到 $\red{n ，}$每一位少女有自己的魅力值 $\red{a_i}$（未知），每个人 的魅力值最大为 $\red{2^{20} - 1 = 1048575}$。

歌剧的舞台不是一个人的舞台，默契值是歌剧质量的重要标准，两位少女的默契值 是她们魅力值按位与后的结果 $\red{a_i\&a_j}$。

露崎真昼现在已知了 $\red{m }$对少女的默契值，但这样可能有多种情况，她想让编号靠前 的舞台少女魅力值尽量大，即魅力值的字典序最大。她想让你找出这个最大的情况，输 出每一位少女的魅力值。

输入格式

第一行两个整数 $\red{n, m}$。

接下来 $\red{m }$行每行输入三个数 $\red{x, y, z，}$表示编号为 $\red{x }$的少女与编号为 $\red{y }$的少女默契值 为 $\red{z}$。

输入数据保证有解，保证 $\red{x ≠ y}$。

输出格式

输出 $\red{n }$个数，空格隔开，即每一位少女的魅力值 $\red{a_i}$。

样例

输入样例

4 2
1 4 7
2 4 3

输出样例

1048575 1048571 1048575 7

提示

对于 $\red{30\% }$的数据，$\red{1 ≤}$ $\red{n ≤}$ $\red{6}$; $\red{1 ≤}$ $\red{m ≤}$ $\red{10}$; $\red{0 ≤}$ $\red{z ≤}$ $\red{10}$。

对于 $\red{50\% }$的数据，$\red{1 ≤}$ $\red{n ≤}$ $\red{10}$; $\red{1 ≤}$ $\red{m ≤}$ $\red{30}$; $\red{0 ≤}$ $\red{z ≤}$ $\red{2^{20} - 1}$。

对于所有的数据，$\red{1 ≤}$ $\red{n, m ≤}$ $\red{10^5}$; $\red{1 ≤}$ $\red{x, y ≤}$ $\red{n}$; $\red{0 ≤}$ $\red{z ≤}$ $\red{2^{20} - 1}$。

其中有 $\red{20\% }$的数据满足 $\red{1 ≤}$ $\red{n, m ≤}$ $\red{10^5}$; $\red{0 ≤}$ $\red{z ≤}$ $\red{1}$。