type nod=^node;
    node=record
         x,cost:longint;
         next:nod;
         end;
var d:array[1..5000] of nod;
    costitza:array[1..5000] of longint;
    sol:array[1..5000] of longint;
    i,n,w,t,m,a,b,c:longint;
    f,g:text;
    p,q:nod;
function min(a,b:longint):longint;
begin
if a<b then min:=a else min:=b;
end;
begin
assign(f,'dijkstra.in'); reset(f);
assign(g,'dijkstra.out'); rewrite(g);
readln(f,n,m);
for i:=1 to n do costitza[i]:=-1;
for i:=1 to m do
 begin
 readln(f,a,b,c);
  new(p);
 p^.x:=b;
 p^.cost:=c;
 p^.next:=d[a];
 d[a]:=p;
 {new(p);
 p^.x:=a;
 p^.next:=d[b];
 d[b]:=p;}
 end;
 i:=1; t:=1; sol[i]:=1;   costitza[1]:=0;
 while i<=t do
  begin
  w:=sol[i];
  q:=d[w];
  while  q<>nil do
   begin
   if costitza[q^.x]=-1 then begin t:=t+1; sol[t]:=q^.x;
                                   costitza[q^.x]:=costitza[w]+q^.cost; end
    else begin costitza[q^.x]:=min(costitza[q^.x],costitza[w]+q^.cost) end;
   q:=q^.next;
   end;
   i:=i+1;

  end;
for i:=2 to n do
 write(f,costitza[i],' ');
 close(f); close(g); end.