program mire;
var t:array[0..2,0..250000] of longint;
   start,co,cc,d:array[0..50000] of longint;
   viz:array[1..50000] of 0..1;
   f,g:text;
   n,m,u:longint;
procedure citire;
var i,k,x,y,c:longint;
begin
 assign(f,'bellmanford.in'); reset(f);
   readln(f,n,m);
   k:=0;
   for i:=1 to m do
    begin
      readln(f,x,y,c);
      inc(k);
      t[0,k]:=y;
      t[1,k]:=start[x];
      t[2,k]:=c;
      start[x]:=k;
    end;
 close(f);
end;
procedure bell;
var k,p,nod,aux,i:longint;
begin
  for i:=2 to n do
       d[i]:=maxlongint;
    d[1]:=0;
    co[1]:=1;
    u:=1;
 for k:=1 to n do
   begin
      for i:=1 to u do
       viz[co[i]]:=0;
      aux:=0;
      for i:=1 to u do
        begin
            nod:=co[i];
            p:=start[nod];
            while p<>0 do
              begin
                 if d[nod]+t[2,p]<d[t[0,p]] then
                    begin
                       d[t[0,p]]:=d[nod]+t[2,p];
                       if viz[t[0,p]]=0 then
                         begin
                           viz[t[0,p]]:=1;
                           inc(aux);
                           cc[aux]:=t[0,p];
                         end;
                    end;
                    p:=t[1,p];
              end;
        end;
        for i:=1 to aux do
          co[i]:=cc[i];
        u:=aux;
   end;

end;
function ciclu:boolean;
var  p,i,nod:longint;
     ok:boolean;
begin
ok:=false;
  for i:=1 to u do
    begin
      nod:=co[i];
      p:=start[nod];
      while p<>0 do
        begin
          if d[nod]+t[2,p]<d[t[0,p]] then
            ok:=true;
           p:=t[1,p];
        end;
    end;
  ciclu:=ok;
end;
procedure afis;
var i:longint;
begin
 assign(g,'bellmanford.out'); rewrite(g);
if ciclu then
  write(g,'Ciclu negativ!')
 else
  for i:=2 to n do
   write(g,d[i],' ');
 close(g);
end;
begin
 citire;
 bell;
 afis;
end.