const   fin = 'dijkstra.in'; fout = 'dijkstra.out'; inf = 50000 * 1000 + 1;

type    listamuchii = ^muchie;
        muchie = record
                nod ,cost : longword;
                urm : listamuchii;
        end;
        coada = ^noduri;
        noduri = record
                nod : longword;
                urm : coada;
        end;

        graf = array[1..50000] of listamuchii;
        costuri = array[1..50000] of longword;
        buffer = array[1..1 shl 21] of char;
        bufferout = array[1..1 shl 17] of char;
var
        g : graf;
        c : costuri;
        buf : buffer;
        bufout : bufferout;
        n : longword;

procedure init();
var
        i : longword;
begin
        for i := 1 to n do
        begin
                new(g[i]);
                g[i]^.nod := 0;
                g[i]^.urm := nil;
                c[i] := inf;
        end;
        c[1] := 0;
end;

procedure parcurgegraf();
var
        nod ,q ,qf : coada;
        p : listamuchii;
        x : longword;
begin
        new(q);
        q^.nod := 1;
        q^.urm := nil;
        qf := q;

        while (q <> nil) do
        begin
                x := q^.nod; //setam nodul x din coada
                p := g[x];  //setam lista muchiilor de la nodul x
                while (p^.nod <> 0) do //cit mai avem muchii in lista
                begin
                        if (c[x] + p^.cost < c[p^.nod]) then
                        begin
                                c[p^.nod] := c[x] + p^.cost;
                                new(nod);
                                nod^.nod := p^.nod;
                                nod^.urm := nil;
                                qf^.urm := nod;
                                qf := nod;
                        end;
                        p := p^.urm; //mergem la urmatoare muchie
                end;
                nod := q; q := q^.urm; dispose(nod); //scoatem nodul din coada
        end;
end;

procedure main();
var
        i ,m ,x ,y ,cost : longword;
        nod : listamuchii;
begin
        assign( input, fin ); reset( input );
        assign( output, fout ); rewrite( output );
        settextbuf( input, buf );
        settextbuf( output, bufout );

        readln( n, m );

        init();

        for i := 1 to m do
        begin
                readln( x, y, cost );
                new(nod);
                nod^.nod := y;
                nod^.cost := cost;
                nod^.urm := g[x];
                g[x] := nod;
        end;

        parcurgegraf();

        for i := 2 to n do
        if (c[i] = inf) then write( 0, #32 ) else write( c[i], #32 );
end;


begin
        main();
end.