program fddg;
type mi=record
nod,cost:longint; end;
var i,j,n,m,wnod,wcost,x,y,z,st,sf,nr:longint;
a:array of array of mi;
q,viz,d:array[0..1000001] of longint;
bufin:array[1..65000] of byte;
f,g:text;
begin
assign(f,'bellmanford.in'); reset(f);
assign(g,'bellmanford.out'); rewrite(g);
{settextbuf(f,bufin);  }
  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[st]:=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.