program mire;
var t:array[0..2,0..250000] of longint;
   start,co,cc,d,fr:array[0..50000] of longint;
   viz:array[1..50000] of 0..1;
   f,g:text;
   n,m,u,i:longint;
   ok:boolean;
procedure citire;
var i,k,x,y,c:longint;
begin
 assign(f,'bellmanford.in'); reset(f);
 assign(g,'bellmanford.out'); rewrite(g);
   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(sursa:longint);
var k,p,nod,aux,i,st,sf:longint;
begin
   d[sursa]:=0;
   for i:=2 to n do
     d[i]:=maxlongint;
   st:=0; sf:=1; co[1]:=sursa; ok:=true;
   while (st<sf) and (ok) do
     begin
       inc(st);
       nod:=co[st];
       p:=start[nod];
       viz[nod]:=0;
       while (p<>0) and (ok)  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
                        inc(sf);
                        co[sf]:=t[0,p];
                        viz[t[0,p]]:=1;
                        inc(fr[t[0,p]]);
                      end;
                 end;
              if fr[t[0,p]]>n-1 then
                ok:=false;
             p:=t[1,p];
          end;
     end;
end;
begin
  citire;
  bell(1);
 if not ok then
         write(g,'Ciclu negativ!')
 else
        for i:=2 to n do
                 write(g,d[i],' ');
 close(g);
end.