program bell_man_bun;
const nmax=50001;
      inf=maxlongint;
var t:array[0..2,1..250001] of longint;
    start,d,cd,cc:array[1..nmax] of longint;
    viz:array[1..nmax] of 0..1;
    n,m,nr,ok,st,sf,p,i,j,k,cost,nod:longint;
    f,g:text;

begin
 assign(f,'grader_test4.in'); reset(f);
 assign(g,'bellmanford1.out'); rewrite(g);
 readln(f,n,m);
 for k:=1 to m do
  begin
   readln(f,i,j,cost);
   t[0,k]:=j;
   t[1,k]:=start[i];
   t[2,k]:=cost;
   start[i]:=k;
  end;
 for i:=2 to n do
  d[i]:=inf;
 d[1]:=0; cd[1]:=1;
 st:=1; sf:=1; viz[1]:=0;
 for i:=1 to n do
  while st<=sf do
   begin
    nod:=cd[st];
    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;
          sf:=sf+1;
          cd[sf]:=t[0,p];
         end;
       end;
      p:=t[1,p];
     end;
    st:=st+1;
   end;
 ok:=1;
 for i:=st to sf do
  begin
   nod:=cd[i];
   p:=start[nod];
   while p<>0 do
    begin
     if d[nod]+t[2,p]<d[t[0,p]] then
       ok:=0;
     p:=t[1,p];
    end;
  end;
 if ok=0 then
  write(g,'Ciclu negativ!')
 else
  for i:=2 to n do
   write(g,d[i],' ');
 close(f);
 close(g);
end.