var f:text;
    a:array[1..50000,1..50000] of integer;
    n,m,i,b,c,q,r,min,j:integer;
    d:array[1..250000] of integer;
    ver:array[1..250000] of boolean;
begin
assign(f,'dijkstra.in');
reset(f);
readln(f,n,m);
fillchar(a,sizeof(a),100);
fillchar(d,sizeof(d),100);
for i:=1 to m do
  readln(f,b,c,a[b,c]);
close(f);
ver[1]:=true;
d[1]:=0;
for i:=2 to n do
  if a[1,i]<>25700 then
   d[i]:=a[1,i];
for i:=1 to n do
 begin
  min:=maxint;
  for j:=1 to n do
    if (ver[j]=false) and (d[j]<min)  then
     begin
      min:=d[j];
      r:=j;
     end;
  ver[r]:=true;
  for j:=1 to n do
   if (ver[j]=false) and (d[j]>d[r]+a[r,j]) then
    d[j]:=d[r]+a[r,j];
 end;
assign(f,'dijkstra.out');
rewrite(f);
for i:= 2 to n do
 write(f,d[i],' ');
close(f);
end.