program asd;

type muchie=record nod, cost:longint; end;

var fi,fo:Text;
    a:Array of Array of muchie;
    cd,d,viz:array[1..1000000] of longint;
    n,m:longint;
    bufin,bufout:array[1..65000] of byte;

    procedure citire_date;
    var i,x,y,z,poz:longint;
    begin
        readln(fi,n,m);
        setlength(a,n+1);

        for i:=1 to n do
          setlength(a[i],1);

        for i:=1 to m do
          begin
              readln(fi,x,y,z);

              //cresc lungimea vectorului care retine vecinii lui x
              setlength(a[x], length(a[x])+1);

              //actualizez "lungimea" listei de vecini a lui x
              //retinuta pe pozitia 0 a vectorului
              a[x,0].nod:=a[x,0].nod+1;

              poz:=a[x,0].nod; //pozitia unde voi pune urmatorul vecin al lui x

              a[x,poz].nod:=y;
              a[x,poz].cost:=z;

          end;
    end;

    procedure initializare_vector_lungimi;
    var i:longint;
    begin
        for i:=1 to n do
          d[i]:=maxint;
    end;

    procedure determinare;
    var ps,pi,nodstart,el,poz,i,nod,cost:longint;
    begin
        ps:=1; pi:=1; nodstart:=1;
        cd[ps]:=nodstart;
        d[nodstart]:=0;

        while ps<=pi do
          begin
              //la fiecare pas, se scoate un nod din coada (el) si se gasesc
              //toate nodurile i a caror distanta de la sursa la acestea
              //poate fi optimizat prin intermediul nodului el.
              //daca nodul w nu se afla deja in coada, el este adaugat.

              el:=cd[ps]; //scot din coada
              poz:=a[el,0].nod; //pana la ce pozitie sunt vecini ai lui el in mat

              for i:=1 to poz do
                begin
                    nod:=a[el,i].nod;
                    cost:=a[el,i].cost;
                    if d[nod]>d[el]+cost then
                      begin
                          d[nod]:=d[el]+cost;
                          viz[nod]:=1;
                          inc(pi);
                          cd[pi]:=nod;
                      end;
                end;

              inc(ps);

          end;
    end;

    procedure scriere;
    var i:longint;
    begin
        for i:=2 to n do
          begin
              if d[i]=maxint then
                d[i]:=0;
              write(fo,d[i],' ');
          end;
    end;

begin
    assign(fi,'dijkstra.in'); reset(fi);
    settextbuf(fi,bufin);
    assign(fo,'dijkstra.out'); rewrite(fo);
    settextbuf(fo,bufout);

        citire_date;

        initializare_vector_lungimi;

        determinare;

        scriere;

    close(Fi); close(Fo);
end.