program diejkstra;
type  dint = record
             nod : integer;
             cost : longint;
             end;
      pnod = ^nod;
      nod = record
            info : dint;
            urm : pnod;
            end;
var A,ultim : array [1..50000] of pnod;
    urm : pnod;
    H : array [1..50000] of dint;
    D : array [1..50000] of longint;
    i,j,m,n,lvl,x,y : word;
    f,g : text;

procedure shift(n,x:word);
var son : word;
    c : dint;
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[son].cost>H[x].cost then son := 0;
                end;
if son<>0 then begin
               c := H[x];
               H[x] := H[son];
               H[son] := c;
               x := son;
               end;
until son=0;
end;

procedure percolate(x:word);
var c : dint;
begin
if x>1 then
if H[x].cost>H[x div 2].cost 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(val:dint);
begin
lvl := lvl+1;
H[lvl] := val;
percolate(lvl);
end;

procedure dijkstra;
var k : word;
begin
while lvl<>0 do begin

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

end;


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

readln(f,n,m);
lvl := 0;
for i := 1 to n do begin
D[i] := 50000000;
A[i] := nil;
end;

for i := 1 to m do begin
read(f,x);
if A[x]=nil then begin
                 new(A[x]);
                 readln(f,A[x]^.info.nod,A[x]^.info.cost);
                 A[x]^.urm := nil;
                 ultim[x] := A[x];
                 end
else begin
     new(urm);
     readln(f,urm^.info.nod,urm^.info.cost);
     ultim[x]^.urm := urm;
     ultim[x] := urm;
     end;
end;


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

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

dijkstra;

for i := 2 to n do
if D[i]=50000000 then write(g,'0 ')
                 else write(g,D[i],' ');
close(f);
close(g);
end.