const inf=250000002;
type ref=^lista;
     lista=record
           vf:word;
           c:longint;
           leg:ref;
           end;

var g:array[1..50000] of ref;
    h,poz:array[1..50000] of word;
    d:array[1..50000] of longint;
    n,x0,nv:word;
    m:longint;

procedure adauga(x,y,c:word);
var p:ref;
begin
new(p);p^.vf:=y;p^.c:=c;p^.leg:=g[x];g[x]:=p;
end;

procedure citeste;
var x,y,c:word;
    i:longint;
begin
assign(input,'dijkstra.in');reset(input);
readln(n,m);
for i:=1 to m do
begin
readln(x,y,c);
adauga(x,y,c);
end;
i:=1;
nv:=n;
close(input);
end;

procedure comb(i,n:word);
var l,r:longint;
    aux,go:word;
begin
l:=2*i;r:=2*i+1;
go:=i;
if (l<=n) and (d[h[l]]<d[h[i]]) then go:=l;
if (r<=n) and (d[h[r]]<d[h[i]]) and (d[h[r]]<d[h[go]]) then go:=r;
if go<>i then begin
             aux:=h[go];
             h[go]:=h[i];
             h[i]:=aux;
             poz[h[go]]:=go;
             poz[h[i]]:=i;
             comb(go,n);
             end;
end;


procedure heapup(k:word);
var aux:word;
begin
if (k div 2>0) and (d[h[k div 2]]>d[h[k]]) then
                begin
                aux:=h[k];
                h[k]:=h[k div 2];
                h[k div 2]:=aux;
                poz[h[k]]:=k;
                poz[h[k div 2]]:=k div 2;
                heapup(k div 2);
                end;
end;


function elim:word;
var aux:word;
begin
elim:=h[1];
aux:=h[1];
h[1]:=h[nv];
h[nv]:=aux;
dec(nv);
comb(1,nv);
end;

procedure formheap;
var i:word;
begin
for i:=nv div 2 downto 1 do
comb(i,nv);
end;

procedure dijkstra;
var p:ref;
    i,k:word;
begin
p:=g[x0];
for i:=1 to n do
begin
d[i]:=inf;
h[i]:=i;
poz[i]:=i;
end;

while p<>nil do
 begin
 d[p^.vf]:=p^.c;
{ heapup(poz[p^.vf]);}
 p:=p^.leg;
 end;
formheap;
k:=5;
while (nv>0)  do
 begin
 k:=elim;if d[k]=inf then exit;
  p:=g[k];
 while p<>nil do begin
  if d[k]+p^.c<d[p^.vf] then  begin
                            d[p^.vf]:=d[k]+p^.c;
                            heapup(poz[p^.vf]);
                            end;
  p:=p^.leg;

  end;
  end;
end;


procedure afisare;
var i:word;
begin
assign(output,'dijkstra.out');rewrite(output);
for i:=2 to n do
if d[i]<inf then write(d[i],' ')
                else write(0, ' ');
close(output);
end;

begin
citeste; x0:=1;
dijkstra;
afisare;
end.