var t:array[1..50005,1..50005] of longint;
    v,viz,TT:array[1..50005] of longint;
    n,m,i,j,p,a,b,x,min,mx,poz:longint;
begin
assign(input,'dijkstra.in'); reset(input);
assign(output,'dijkstra.out'); rewrite(output);
readln(n,m);
for i:=1 to m do
 begin
  readln(a,b,x);
  t[a,b]:=x
 end;
mx:=1000000000;
for i:=1 to n do
 for j:=1 to n do
  if i=j then t[i,j]:=0 else
  if t[i,j]=0 then t[i,j]:=mx;
viz[1]:=1;
for i:=2 to n do
 begin
  v[i]:=t[1,i];
  if t[1,i]<mx then TT[i]:=p
 end;
for i:=1 to n-1 do
 begin
  min:=mx;
  for j:=1 to n do
   if (v[j]<min) and (viz[j]=0) then
    begin
     min:=v[j];
     poz:=j
    end;
  viz[poz]:=1;
  for j:=1 to n do
   if (viz[j]=0) and (v[poz]+t[poz,j]<v[j]) then
    begin
     v[j]:=v[poz]+t[poz,j];
     TT[j]:=poz
    end
 end;
for i:=2 to n do write(v[i],' ');
close(input);
close(output)
end.