program cogs1787;
type nyd=record
     n,y,d:longint;
end;
var
   du,a,q,d,c:array[0..1100]of longint;
   b:array[0..12000]of nyd;
   bb:array[0..1100]of boolean;
   tt,max,ans,p,i,h,t,n,m,x,y,z:longint;
procedure init;
begin
     assign(input,'ExamStat.in');reset(input);
     assign(output,'ExamStat.out');rewrite(output);
end;
procedure add(x,y,d:longint);
begin
     inc(t);
     b[t].d:=d;b[t].y:=y;
     b[t].n:=a[x];a[x]:=t;
end;
procedure main;
begin
     readln(n,m);
     for i:=1 to m do
     begin
          readln(x,y,z);
          if z<0 then add(x,y,-z);
          if z>=0 then add(y,x,z);
     end;
     h:=0;t:=1;fillchar(d,sizeof(d),$0f);
     d[1]:=0;bb[1]:=true;q[1]:=1;
     while h<>t do
     begin
          inc(h);if h>1000 then h:=1;
          x:=q[h];p:=a[x];
          while p<>0 do
          begin
               y:=b[p].y;
               if (d[y]>d[x]+b[p].d) then
               begin
                    d[y]:=d[x]+b[p].d;
                    if not bb[y] then
                    begin
                         inc(t);if t>1000 then t:=1;
                         q[t]:=y;
                         bb[y]:=true;
                         inc(c[y]);
                         if c[y]>=n then begin writeln('SOMEONE LAY!');exit;end;
                    end;
               end;
               p:=b[p].n;
          end;
          bb[x]:=false;
     end;
     for i:=1 to n do writeln(d[i]);
     ans:=maxlongint;
     for i:=1 to n do if d[i]<ans then ans:=d[i];
     if ans<0 then for i:=1 to n do inc(d[i],-ans);
     if ans>0 then for i:=1 to n do dec(d[i],ans);
     for i:=1 to n do if i<>n then write(d[i],' ') else writeln(d[i]);
end;
begin
     init;
     main;
end.