题目描述 1s 512MB

小明有 $n$ 个变量 $x_1,x_2,...,x_n$，每个变量里面存着一个整数。

小明记录了如下 $m$ 条记录，记录形如：

i j v，表示 $a_i-a_j=v$。

但是这里面有一些记录是错的，也就是并不符合 $a_i-a_j=v$。

现在，告诉你这 $m$ 条记录，请帮助小明确认一下，这 $m$ 条记录是否正确，如果这 $m$ 条记录没有产生矛盾，则输出 $0$，然后在下一行输出一组满足条件的构造方案，否则输出一个最小的数字 $i$ 表示前 $i$ 条记录就已经产生了矛盾。

输入格式

第一行输入 $n,m$。

接下来 $m$ 行，每行输入 $i,j,v$ 表示一条记录。

输出格式

如果有解，在第一行输出 $0$，然后在下一行输出 $x_1,x_2,...,x_n$ 表示答案，两个数字之间用空格隔开，如果有多解，输出任意一组即可，你需要保证输出的 $-10^{15}\leq x_i\leq 10^{15}$。

样例输入 #1

3 5
3 1 2
3 2 1
2 1 1
1 2 -1
1 3 2

样例输出 #1

5

样例解释 #1

前 $4$ 条记录都是符合题意的，构造 $x_1=1,x_2=2,x_3=3$ 即可，第 $5$ 条记录显然无法与前 $4$ 条记录同时被满足。

样例输入 #2

3 4
3 1 2
3 2 1
2 1 1
1 2 -1

样例输出 #2

0
1 2 3 

样例输入 #3

8 7
5 1 1
5 7 -1
1 8 0
5 6 -1
2 4 0
4 2 0
5 7 -1

样例输出 #3

0
0 0 0 0 1 2 2 0 

大样例方便调试

数据范围

本题共 20 个测试点

特殊性质 A：对于前 $n-1$ 条记录中的每一条，满足对于第 $i$ 条，$u=i,v=i+1$。

特殊性质 B：保证所有记录一定都是合法的。

对于 100% 的数据：$n\leq 10^5,m\leq 2\times 10^5,1\leq i,j\leq n,i\neq j,|v|\leq 10^9$。