program bellman;

var     bufin,bufout:array[1..750002] of byte;
        start,viz,fr,d:array [1..50000] of longint;
        t:array[0..2,1..500001] of longint;
        cd:array [1..500000] of longint;
        ok:boolean;
        nod,st,sf,x,y,v,i,j,n,m,k,p:longint;

begin
  assign(input,'bellmanford.in'); reset(input);
  assign(output,'bellmanford.out'); rewrite(output);
  readln(n,m); k:=0;
  for i:=1 to m do
    begin
      readln(x,y,v);
      inc(k);
      t[0,k]:=y;
      t[1,k]:=start[x];
      start[x]:=k;
      t[2,k]:=v;
    end;
  for i:=2 to n do
    d[i]:=maxlongint;
  d[1]:=0; st:=0; sf:=1; cd[1]:=1; ok:=true;
  while (st<sf) and  (ok=true) do
    begin
       inc(st); nod:=cd[st]; viz[nod]:=0; p:=start[nod];
       while (p<>0) and (ok=true) 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);
                   cd[sf]:=t[0,p];
                   fr[t[0,p]]:=fr[t[0,p]]+1;
                   viz[t[0,p]]:=1;
                 end;
             end;
           if fr[t[0,p]]>n-1 then
             ok:=false;
           p:=t[1,p];
         end;
    end;
  if ok then
    for i:=2 to n do
      if d[i]<maxint then write(d[i],' ')
        else write(0,' ')
  else
    write('Ciclu negativ!');
  close(input); close(output);
end.