1787. 月考统计

【题目描述】

    S校高二年级丧心病狂的第一次月考已经告一段落。由于考试命题不太合理，学校决定不印发成绩单。这可急坏了班主任$CQW$老师。毕竟，这个班级刚刚组建，班主任需要了解同学们的大致状况，以制定合适的教学方式。于是，常老师决定随机向一些同学了解情况。为避免尴尬，每位同学都只会给$CQW$老师提供成绩的相对值（即自己的成绩比某同学的成绩高多少）。但由于同学们都希望给老师留下好印象，个别同学可能会虚报自己的成绩。当然，他们都不会将自己的成绩报低。

    已知$CQW$老师班里共有$N$名同学，从1到N依次编号。每位同学会告诉老师自己的成绩与若干同学的成绩之差。$CQW$老师把这些信息汇总成了一张表格。这张表共有$M$行，每一行有三个整数$i,j和a_{ij}$，表示第 i 名同学的成绩最多比第 j 名同学高$a_{ij}$分。保证所有同学的分数均为非负整数。

    $CQW$老师希望根据这份表格得出每位同学的成绩与全班最低成绩之差的最小值。作为班里的算法高手，你接下了这个任务。

【输入格式】

第一行有两个正整数$N,M$，分别表示学生的个数和统计表的行数。

接下来有$M$行，第$i+1$行有三个整数$x, y, a_{xy}$，表示第x名同学最多比第y名同学高$a_{xy}$分。

【输出格式】

输出数据有1行。

若无解，输出"SOMEONE LAY!" （不含引号）(英语巨弱的出题人Asm.Def当时脑抽还去Google百度了一下LIE的过去时可却还是写错了……先按这个输出吧……）；

若有解，输出N个整数，第 i 个数为$d_i$，表示第i名同学的分数最少比最后一名同学高$d_i$分。若第i名同学的分数未知，则输出$d_i$为-1.

【样例输入1】

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

 【样例输出1】

SOMEONE LAY!

【样例输入2】

4 6
4 3 2
2 1 5
2 4 3
2 3 -5
4 1 -1
4 2 5

【样例输出2】

1 0 5 0

【数据范围】

\( 对于20 \%的数据，1 \le N \le 15，1 \le M \le 100，保证所有分数的差值绝对值均不大于2；\)

\( 对于50 \%的数据，1 \le N \le 200，1 \le M \le 5000，所有分数的差值绝对值均不大于20；\)

\( 对于100\%的数据，1 \le N \le 1000，1 \le M \le 10000，分数的差值绝对值不大于65535。\)