program bellman_cu_bellman;
const inf=maxlongint;

var t:array[0..2,1..250000] of longint;
    start,viz,d,count:array[1..50000] of longint;
    i,j,n,m,c,x,y,st,dr,k,nod,p:longint;
    cd:array[1..500000] of longint;
    bufin,bufout:array[1..750000] of byte;
    ok:boolean;

begin
  assign(input,'bellmanford.in'); reset(input);
  assign(output,'bellmanford.out'); rewrite(output);
  settextbuf(input,bufin);
  settextbuf(output,bufout);
  readln(n,m);
  k:=0;
  for i:=1 to m do
    begin
      readln(x,y,c);
      inc(k);
      t[0,k]:=y;
      t[1,k]:=start[x];
      start[x]:=k;
      t[2,k]:=c;
    end;

  for i:=1 to n do
    begin
       d[i]:=inf;
    end;
  viz[1]:=1;
  d[1]:=0;
  st:=0;
  dr:=1;
  cd[1]:=1;
  ok:=true;
  while (st<dr) and (ok) do
    begin
      inc(st);
      viz[cd[st]]:=0;
      nod:=cd[st];
      p:=start[nod];
      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(dr);
                  inc(count[t[0,p]]);
                  cd[dr]:=t[0,p];
                  viz[t[0,p]]:=1;
                end;
            end;
          if count[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]=inf then
      write(0,' ')
        else
      write(d[i],' ')
       else
         write('Ciclu negativ!');


  close(input); close(output);
end.