字符串构造机

时间限制: 1s

空间限制: 256M

输入文件: b.in

输出文件: b.out

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

将 $S$ 的字符从1开始依次编号，设 $n=|S|$ ，记 $S_{i, j}$ 表示 $S$ 的第 $i$ 个字符到第 $j$ 个字符构成的子串，定义：

\operatorname{LCP}(i, j)=\max _{i+k \leq n, j+k \leq n, S_{i, i+k}=S_{j, j+k}}\{k+1\}

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

LCP(x_i, y_i)=z_i

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

第一行两个整数 $n, m$ ，表示字符串长度，信息个数

然后 $m$ 行，每行三个整数 $x_i, y_i, z_i$ ，描述一条信息

保证 $x_i+z_i-1, y_i+z_i-1 \leq n$

输出满足条件的字典序最小的字符串，两个字符 （非负整数） 之间用空格隔开，如果不存在这样的字符串，输出一行一个整数 -1

3 2
1 2 0
1 3 1

0 1 0

3 2
1 2 0
1 2 1

-1

对于所有数据点 $1\leq m\leq 1000$ ，下面给出每个数据点的限制：