题目描述

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

样例

样例输入 1

3 2
1 2 0
1 3 1

样例输出 1

0 1 0

样例输入 2

3 2
1 2 0
1 2 1

样例输出 2

-1

数据范围与提示

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

$\#$	$n=$	特殊性质
1	5
2	6
3	7
4	9
5	30	答案为-1
6	100
7	200	$z_i=0$
8	1000
9
10