const inf=maxint;
var a:array[1..5000,1..5000] of integer;
    i,j,k,n,poz,min,m,c:integer;
    d,use:array[1..5000] of integer;
    f,g:text;

procedure citire;
begin
assign(f,'dijkstra.in');
reset(f);


read(f,n,m);

for k:=1 to n do
 for j:=1 to n do a[k,j]:=maxint;
for k:=1 to m do
   begin
   read(f,i,j,c);
   a[i,j]:=c;
   end;
close(f);
end;

procedure dijkstra;
begin
for i:=2 to n do
 d[i]:=a[1,i];
for i:=1 to n-1 do
    begin
    min:=inf;
    for j:=1 to n do
      if (d[j]<min) and (use[j]=0) then
      begin
      min:=d[j];
      poz:=j;
      end;
    use[poz]:=1;
    for j:=1 to n do
        if use[j]=0 then
          if d[j]>d[poz]+a[poz,j] then
             d[j]:=a[poz,j]+d[poz];
     end;
end;

begin
citire;
dijkstra;
assign(g,'dijkstra.out');
rewrite(g);
 for i:=2 to n do write(g,d[i],' ');
close(g);

end.