比赛场次 251
比赛名称 20141105
比赛状态 已结束比赛成绩
开始时间 2014-11-05 08:00:00
结束时间 2014-11-05 12:00:00
开放分组 全部用户
注释介绍 NOIP2014提高组冲刺模拟赛·11月5日
题解已贴在 http://www.cnblogs.com/Asm-Definer/
题目名称 月考统计
输入输出 ExamStat.in/out
时间限制 1000 ms (1 s)
内存限制 256 MiB
测试点数 20 简单对比
用户 结果 时间 内存 得分
Gravatarcstdio AAAAAAAAAAAAAAAAAAAA
0.523 s 0.33 MiB 100
GravatarEzoi_XY AAAAAAAAAAAAAAAAAAAA
0.593 s 0.42 MiB 100
GravatarDijkstra AAAAAAAAAAATATATATAT
5.141 s 4.14 MiB 75
Gravatar东方老败 WAWAWAWAWAWAWAWAWAWA
0.000 s 0.00 MiB 50
GravatarWW TT WAWAWAWAWAWAWAWAWAWA
0.003 s 0.17 MiB 50
Gravatarggwdwsbs WAWAWAWAWAWAWAWAWAWA
0.005 s 0.27 MiB 50
Gravatarok WAWAWAWAWAWAWAWAWAWA
0.008 s 0.30 MiB 50
GravatarSTARGAZER WAWAWAWAWAWAWAWAWAWA
0.008 s 0.30 MiB 50
Gravatar清羽 WAWAWAWAWAWAWAWAWAWA
0.008 s 0.31 MiB 50
GravatarIostream3100 WAWAWAWAWAWAWAWAWAWA
0.012 s 0.31 MiB 50
GravatarHuskar WAWAWAWAWAWAWAWAWAWA
0.014 s 0.30 MiB 50
GravatarRa-xp WAWAWAWAWAWAWAWAWAWA
0.017 s 0.30 MiB 50
Gravatarmikumikumi WAWAWAWAWAWAWAWAWAWA
0.019 s 0.31 MiB 50
Gravatar今天真冷哎 目测一题要E二三要W WAWAWAWAWAWAWAWAWAWA
0.021 s 0.15 MiB 50
Gravatar黑駒 WAWAWAWAWAWAWAWAWAWA
0.027 s 0.17 MiB 50
GravatarCirno AAAAAAAAAAWWWWWWWWWW
0.093 s 0.39 MiB 50
Gravatar冷颜少年 WAWAWAWAWAWAWAWAWAWA
0.259 s 3.81 MiB 50
GravatarSatoshi C 0.000 s 0.00 MiB 0
Gravatar稠翼 WWWWWWWWWWWWWWWWWWWW
0.081 s 0.32 MiB 0

月考统计

★★☆   输入文件:ExamStat.in   输出文件:ExamStat.out   简单对比
时间限制:1 s   内存限制:256 MiB

【题目描述】


    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。\)