program Djikastra;
VAR c:array[1..1000,1..1000] of longint;
    i,x,y,j:integer;
    f,g:text;
    d:array[1..1000] of longint;

procedure djik(x0:integer);
VAR i,k:integer;
    min:longint;
    viz:array[1..1000] of integer;
    ok:boolean;
BEGIN
        for i:=1 to n do
                begin
                viz[i]:=0;
                d[i]:=c[x0][i];
                end;
        viz[x0]:=1;
        ok:=true;
        while ok do
                begin
                min:=200000;
                for i:=1 to n do
                        if (viz[i]=0) and (min>d[i]) then
                                begin
                                min:=d[i];
                                k:=i;
                                end;
                if min<>200000 then
                        begin
                        viz[k]:=1;
                        for i:=1 to n do
                                if (viz[i]=0) and (d[i]>d[k]+c[k][i]) then
                                        begin
                                        d[i]:=d[k]+c[k][i];
                                        end;
                                        end else ok:=false;
end;
end;

procedure afisare();
begin
        for i:=2 to n do
        write(g,d[i],' ');
end;

BEGIN
        assign(f,'djikastra.in'); Reset(f);
        assign(g,'djikastra.out'); Rewrite(g);
        readln(f,n,m);
        for i:=1 to m do
                for j:=1 to m do
                        c[i][j]:=200000;
        for i:=1 to m do
                read(f,x,y,c[x,y]);
        djik(1);
        afisare();
        Close(g);
END.