program dijkstra;{heap version :P}
const inf = 50000000;
type pnod = ^nod;
      nod = record
            info,cost : word;
            urm : pnod;
            end;
var A,H : array [1..50000] of pnod;
    D : array [1..50000] of longint;
    urm : pnod;
    n,x,y,c,lvl : word;
    i,m : longint;
    f,g : text;

procedure shift(n,x:longint);
var son : longint;
    c : pnod;
begin
repeat
son := 0;
if 2*x<=n then begin
                son := 2*x;
                if 2*x+1<=n then if H[2*x]^.cost>H[2*x+1]^.cost then son := 2*x+1;
                if H[x]^.cost<=H[son]^.cost then son := 0;
                end;
if son<>0 then begin
               c := H[son];
               H[son] := H[x];
               H[x] := c;
               x := son;
               end;
until son=0;
end;

procedure percolate(x:word);
var c : pnod;
begin
if x>1 then
if H[x div 2] > H[x] then begin
                          c := H[x];
                          H[x] := H[x div 2];
                          H[x div 2] := c;
                          percolate(x div 2);
                          end;
end;

procedure delete;
begin
H[1] := H[lvl];
lvl := lvl-1;
shift(lvl,1);
end;

procedure add(x:pnod);
begin
lvl := lvl+1;
H[lvl] := x;
percolate(lvl);
end;

procedure dijkstra;
var k : word;
begin

while lvl<>0 do begin

k := H[1]^.info;
delete;

urm := A[k];
while urm<>nil do begin
if D[urm^.info] > D[k]+urm^.cost then begin
                                        D[urm^.info] := D[k]+urm^.cost;
                                        add(urm);
                                        end;
urm := urm^.urm;
end;
end;
end;

begin
assign(f,'dijkstra.in');
reset(f);
assign(g,'dijkstra.out');
rewrite(g);

readln(f,n,m);
for i := 1 to n do
D[i] := inf;

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

urm := A[1];
lvl := 0;
while urm<>nil do begin
lvl := lvl+1;
H[lvl] := urm;
D[urm^.info] := urm^.cost;
urm := urm^.urm;
end;

for i := lvl div 2 downto 1 do
shift(lvl,i);


dijkstra;

for i := 2 to n do
if D[i]<>inf then write(g,D[i],' ')
             else write(g,'0 ');

close(f);
close(g);


end.