type point=^nod;
     nod=record
         nr,d:longint;
         ua:point;
     end;
     loch=record
          d,p:longint;
     end;

var f1,f2:text;
    i,n,m,g,t,f,c,dh,min,lc,cn,ds:longint;
    p:point;
    l:array[0..50010] of point;
    d,hp:array[0..100010] of loch;

procedure swap(i,j:longint);
var aux:loch;
begin
        aux:=hp[i];
        hp[i]:=hp[j];
        hp[j]:=aux;
        d[i].p:=j;
        d[j].p:=i;
end;

procedure clad(t,f,c:longint);
begin
        new(p);
        p^.nr:=f;
        p^.d:=c;
        p^.ua:=l[t];
        l[t]:=p;
end;

procedure heapup(i:longint);
begin
        if i>1 then
                if hp[i div 2].d>hp[i].d then
                begin
                        swap(i,i div 2);
                        heapup(i div 2);
                end;
end;

procedure heapdown(i,n:longint);
var f:longint;
begin
        if 2*i<=dh then
        begin
                f:=2*i;
                if (2*i+1<=dh)and(hp[2*i+1].d<hp[2*i].d) then
                        inc(f);
                if hp[i].d>hp[f].d then
                begin
                        swap(i,f);
                        heapdown(f,n);
                end;
        end;
end;

begin
        assign(f1,'dijkstra.in');
        reset(f1);
        assign(f2,'dijkstra.out');
        rewrite(f2);
        read(f1,n,m);
        for i:=1 to m do
        begin
                read(f1,t,f,c);
                clad(t,f,c);
        end;
        for i:=2 to n do
                d[i].d:=maxint;
        p:=l[1];
        dh:=0;
        while p<>nil do
        begin
                inc(dh);
                d[p^.nr].d:=p^.d;
                d[p^.nr].p:=dh;
                hp[dh].d:=p^.d;
                hp[dh].p:=p^.nr;
                heapup(dh);
                p:=p^.ua;
        end;
        for g:=1 to n-1 do
        begin
                min:=hp[1].p;
                cn:=hp[1].d;
                hp[1].d:=-1;
                p:=l[min];
                while p<>nil do
                begin
                        lc:=p^.nr;
                        ds:=p^.d;
                        if d[lc].d>cn+ds then
                        begin
                                d[lc].d:=cn+ds;
                                if d[lc].p=0 then
                                begin
                                        inc(dh);
                                        hp[dh].p:=lc;
                                        d[lc].p:=dh;
                                end;
                                hp[d[lc].p].d:=d[lc].d;
                                heapup(d[lc].p);
                        end;
                        p:=p^.ua;
                end;
                hp[1]:=hp[dh];
                dec(dh);
                heapdown(1,dh);
        end;
        for i:=2 to n do
                if d[i].d<>maxint then
                        write(f2,d[i].d,' ')
                else write(f2,0,' ');
        close(f1);
        close(f2);
end.