program asss;
type mi=record
    nod,cost:longint;
    end;
var f,g:text;
    n,m,i,j,wnod,wcost,pi,ps,x,y,z,nr:longint;
    d,q:array[1..5000005] of longint;
    a:array of array of mi;
begin
  assign(f,'dijkstra.in'); reset(f);
  assign(g,'dijkstra.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;
      pi:=1;
      ps:=1;
      q[pi]:=1;
      d[1]:=0;
        for i:=2 to n do
          d[i]:=maxlongint;
            while ps<=pi do
              begin
              nr:=q[ps];
              ps:=ps+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;
                        pi:=pi+1;
                        q[pi]:=wnod;
                        end;
                  end;
              end;
          for i:=2 to n do
          begin
            if d[i]=maxlongint then
              d[i]:=0;
            write(g,d[i],' ');
          end;
  close(f);
  close(g);
end.