program dijkstra;

type lista=^elem;
     elem=record
      cs,c:longint;
      kov:lista;
     end;

var x:array[1..50001] of lista;
    tav:array[1..50001] of longint;
    latott:array[1..50001] of boolean;
    n,m,i,a,b,c:longint;
    f:text;

procedure betesz(var s:lista; b,c:longint);
var uj:lista;
begin
 new(uj);
 uj^.cs:=b;
 uj^.c:=c;
 uj^.kov:=s;
 s:=uj;
end;

procedure dijkstra(kezd:longint);
var p:lista;
    ok:boolean;
    i,min,m:longint;
begin
 for i:=1 to n do begin
  tav[i]:=MAXLONGINT;
  latott[i]:=false;
 end;
 tav[kezd]:=0;
 ok:=true;
 while (ok=true) do begin
  min:=-1; m:=MAXLONGINT;
  for i:=1 to n do
   if (not latott[i]) and (tav[i]<m) then begin
    m:=tav[i];
    min:=i;
   end;
  if min=-1 then ok:=false
  else begin
   latott[min]:=true;
   p:=x[min];
   while (p<>nil) do begin
    if (not latott[p^.cs]) and (tav[min]+p^.c<tav[p^.cs]) then tav[p^.cs]:=tav[min]+p^.c;
    p:=p^.kov;
   end;
  end;
 end;
end;

begin
assign(f,'dijkstra.in');
reset(f);
readln(f,n,m);
for i:=1 to m do begin
 readln(f,a,b,c);
 betesz(x[a],b,c);
end;
close(f);

dijkstra(1);

assign(f,'dijkstra.out');
rewrite(f);
for i:=2 to n do
 if (tav[i]=MAXLONGINT) then write(f,'0 ')
 else write(f,tav[i],' ');
close(f);
end.