#B0004. 小杨忘密码

小杨忘密码

题目背景

小杨为了防止别人JC他,给自己的电脑创建了nn位英文大写字母和数字混合的密码aa,别人没猜出来,他也忘了......

题目描述

很幸运的是,小杨在玩他的密码的时候,记录了几对两位之间的asciiascii码差,例如x1x2=3x_1-x_2=3

小杨希望你通过这些asciiascii码差推断出他的密码,作为奖励,他会给你AKIOI的神器。

输入格式

11行,两个数nnmm,表示小杨密码的长度和他记得的对数。

接下来mm行,每行三个数uuvvww,表示auav=wa_u-a_v=w

输出格式

如果无解,请输出1-1

否则,输出一行字符串ss,表示密码。

如果有多组解,输出其中asciiascii码和最小的一组。

3 3
1 2 9
2 3 10
1 3 19
JA7

提示/说明

对于90%90\%的数据,保证1n,m1051\le n,m \le 10^5

对于另外10%10\%的数据,保证1n,m1061\le n,m \le 10^6