该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

原神场怎么能没有原神题？

某兔：我是石器时代的狼王！原始人，启动！我是山里灵活的狗！

鉴定为玩原神玩的。

题目背景

你又双叒叕被 七国集团（难绷） 尘世七执政通缉了！原因是你勾结坎瑞亚叛党，意图谋反，祸乱尘世，罪不容诛！

好吧，其实是某天你从地底下挖出来了一个坎瑞亚古国的超级兵器——二次复合态派蒙自动机！它轻而易举地爆发出了来自远古的坎瑞亚之力。所以你就被通缉了。

但芭芭拉的演唱会还没看过，你怎么能甘心被关进大牢里呢？因此你希望向审判你的水神大人解释清楚二次复合态派蒙自动机的结构。

题目描述

二次复合态派蒙自动机可以看做是一张 $n$ 个结点 $m$ 条边的简单无向图。其中每个点有点权，每条边有边权。其计算方式如下：

• 设点 $i$ 的点权为 $a_i$（未知）。
• 则边 $(u,v)$ 的权为 $a_u~ \mathrm{and} ~a_v$。

其中 $\mathrm{and}$，也即我们常见的 $\&$ ，代表按位与运算。

现在你拿起手里的二次复合态派蒙自动机展示给水神大人看，发现图上所有边的边权已经给出。

现在你需要找出一组合法的点权，使得这 $m$ 条边的边权被满足，或者向水神报告不存在。更详细的信息请查阅【输出格式】。

注意，边权只能在 $0\le a_i< 2^{30}$ 范围内哦~

输入格式

输入的第一行有两个正整数 $n,m$，表示无向图的结点数和边数。

之后 $m$ 行，每行三个整数 $u,v,w$ 表示一条边所连的两个结点以及边权。

输出格式

第一行输出解的存在性，如果存在输出 $1$，否则输出 $0$。

如果解存在，则再输出一行 $n$ 个数 $a_1,a_2,\ldots,a_n$ 表示任意一组点权。

样例 #1

样例输入 #1

3 3
1 2 4
1 3 1
2 3 0

样例输出 #1

1
5 6 17

提示

【数据范围】

对于全体数据，保证 $3\le n\le 10^5$，$1\le m\le 2\times 10^5$，$0\le w<2^{30}$。