program ssss;
type mi=record
nod, cost:longint;
    end;
var f,g:text;
    n,m,i,j,wnod,wcost,x,y,z,st,sf,nr:longint;
    q,d,viz:array[0..10000001] of longint;
    a:array of array of mi;
begin
assign(f,'bellmanford2.in'); reset(f);
assign(g,'bellmanford.out'); rewrite(g);
readln(f,n,m);
setlength(a,n+1,1);
   for i:=1 to m do
     begin
        readln(f,x,y,z);
        setlength(a[x],length(a[x])+1);
        a[x,0]. nod:=a[x,0].nod+1;
        a[x,a[x,0].nod].nod:=y;
        a[x,a[x,0].nod].cost:=z;
     end;
  st:=1;
   sf:=1;
   q[1]:=1;  d[1]:=0;
     for i:=2 to n do
       d[i]:=maxlongint;
      while st<=sf do
        begin
          nr:=q[st];
          st:=st+1;
          viz[nr]:=viz[nr]+1;
            for i:=1 to a[nr,0].nod do
              begin
                wnod:=a[nr,i].nod;
                wcost:=a[nr,i].cost;
                  if d[wnod]>d[nr]+wcost then
                    begin
                    d[wnod]:=d[nr]+wcost;
                    sf:=sf+1;
                    q[sf]:=wnod;
                    viz[wnod]:=viz[wnod]+1;
                      if viz[wnod]>n then
                        begin
                          write(g,'Ciclu negativ!');
                          close(f);
                          close(g);
                          exit;
                        end;
                    end;
              end;
        end;
        for i:=2  to n do
          write(g,d[i],' ');
close(f);
close(g);
end.