program dijkstra;
var d:array of longint;
    s:array[1..50000] of byte;
    a:array of array of integer;
    f,g:text;
    n,m,r:longint;
procedure citire;
var i,j,c,k:longint;
  begin
    readln(f,n,m);
    setlength(a,n+5,n+5);
    setlength(d,n+5);
    for k :=1 to m do
      begin
        readln(f,i,j,a[i,j]);
      end;
  end;
procedure dijkstra;
var i,j,min,poz:longint;
  begin
    s[r]:=1;
    for i:=1 to n do
      for j:=1 to n do
        if (i<>j) and (a[i,j]=0) then
                                 a[i,j]:=maxint;
    for i:=1 to n do
     d[i]:=a[i,r];
    for i:=1 to n-1 do
      begin
        min:=maxint;
        for j:=1 to n do
          if (s[j]=0) and (d[j]<min) then
                                     begin
                                       min:=d[j];
                                       poz:=j;
                                     end;
        s[poz]:=1;
        for j:=1 to n do
          if (s[j]=0) and (d[j]>d[poz]+a[poz,j]) then
                                                 d[j]:=d[poz]+a[poz,j];
      end;
  end;
procedure afisare;
var i:longint;
  begin
    for i:=1 to n-1 do
      write(g,d[i],' ');
  end;
begin
  assign(f,'dijkstra.in');
  assign(g,'dijkstra.out');
  reset(f);
  rewrite(g);
  citire;
  r:=1;
  dijkstra;
  afisare;
  close(f);
  close(g);
end.