题目描述

B 酱发明了通过输入 LCP（Longest Common Prefix，最长公共前缀）信息，输出由非负整数构成的字符串 $S$ 的字符串构造机。

将 $S$ 的字符从 $1$ 开始依次编号，设 $n=|S|$。$\operatorname{LCP}(i,j)$ 表示从位置 $i$ 和位置 $j$ 开始的两个后缀的最长公共前缀长度，即

$$\operatorname{LCP}(i,j)=\max\{\ell\mid 0\le\ell\le\min(n-i+1,n-j+1),\ \forall\,0\le k<\ell,\ S_{i+k}=S_{j+k}\}.$$

长度为 $0$ 的空前缀总是相等；如果两个后缀的首字符不同，则它们的 LCP 为 $0$。

为了测试字符串构造机，B 酱输入了字符串长度 $n$ 和 $m$ 条如下形式的信息：

$$\operatorname{LCP}(x_i,y_i)=z_i.$$

B 酱的字符串构造机需要输出所有满足条件的字符串中，字典序最小的一个。

输入格式

从文件 str.in 中读入数据。

第一行包含两个整数 $n,m$，分别表示字符串长度和信息个数。

接下来 $m$ 行，每行包含三个整数 $x_i,y_i,z_i$，描述一条信息。

输出格式

输出到文件 str.out 中。

输出一行，包含满足条件且字典序最小的字符串，两个字符（非负整数）之间用空格隔开。

如果不存在这样的字符串，输出一行一个整数 -1。

样例 1 输入

3 2
1 2 0
1 3 1

样例 1 输出

0 1 0

样例 1 解释

第一条信息要求第 $1$、$2$ 个字符不同，第二条信息要求第 $1$、$3$ 个字符相同。字典序最小的满足条件的字符串为 $[0,1,0]$。

样例 2 输入

3 2
1 2 0
1 2 1

样例 2 输出

-1

样例 2 解释

两条信息分别要求第 $1$、$2$ 个字符不同和相同，因此无解。

样例 3

见选手目录下的 str/str3.in 与 str/str3.ans。

该样例满足第 $15\sim16$ 个测试点的限制，且 $n=m=1000$，所有 $z_i=0$。

样例 4

见选手目录下的 str/str4.in 与 str/str4.ans。

该样例满足第 $17\sim20$ 个测试点的限制，且 $n=m=1000$。

数据范围

对于所有测试数据，保证 $1\le n,m\le1000$，$1\le x_i,y_i\le n$，$0\le z_i\le\min(n-x_i+1,n-y_i+1)$。

共有 $20$ 个测试点，每个测试点 $5$ 分。

测试点	$n=$	特殊性质
$1\sim2$	$5$	无
$3\sim4$	$6$
$5\sim6$	$7$
$7\sim8$	$9$
$9\sim10$	$30$	答案为 -1
$11\sim12$	$100$	无
$13\sim14$	$200$	所有 $z_i=0$
$15\sim16$	$1000$
$17\sim20$		无