type pmuchie=^muchie;
     muchie=record
       v,c:word;
       next:pmuchie;
     end;

var i,m,n,min,j:longint;
    nr:word;
    h,poz,d:array[0..50004] of word;
    e:array[0..250004] of pmuchie;
    p,nou:pmuchie;
    bufin:array[1..64000] of byte;

procedure swap(a,b:word);
  var c:word;
  begin
     c:=h[a];
     h[a]:=h[b];
     h[b]:=c;
     c:=poz[h[a]];
     poz[h[a]]:=poz[h[b]];
     poz[h[b]]:=c;
  end;

function leftson(k:word):longint;
  begin
    leftson:=k shl 1;
  end;

function rightson(k:word):longint;
  begin
    rightson:=(k shl 1)+1;
  end;

function father(k:word):word;
  begin
    father:=k shr 1;
  end;

procedure sift(n,k:word);
  var son:word;
  begin
    repeat
      son:=0;
      if leftson(k)<=n then begin
        son:=leftson(k);
        if (rightson(k)<=n) and (d[h[rightson(k)]]<d[h[son]]) then
          son:=rightson(k);
        if d[h[son]]>=d[h[k]] then son:=0;
      end;
      if son<>0 then swap(k,son);
      k:=son;
    until son=0;
  end;

procedure percolate(n,k:word);
  begin
    while (k>1) and (d[h[k]]<d[h[father(k)]]) do begin
      swap(k,father(k));
      k:=father(k);
    end;
  end;

begin
  assign(input,'dijkstra.in');
  reset(input);
  settextbuf(input,bufin);
  assign(output,'dijkstra.out');
  rewrite(output);
  readln(n,m);
  for i:=1 to m do begin
    new(nou);
    readln(j,nou^.v,nou^.c);
    nou^.next:=e[j];
    e[j]:=nou;
  end;

  nr:=1;
  poz[1]:=1;
  h[1]:=1;
  for i:=2 to n do d[i]:=64000;
  while nr>0 do begin
    min:=h[1];
    swap(1,nr);
    dec(nr);
    sift(nr,1);
    p:=e[min];
    while p<>nil do begin
      if d[p^.v]>d[min]+p^.c then begin
        d[p^.v]:=d[min]+p^.c;
        if poz[p^.v]=0 then begin
          inc(nr);
          poz[p^.v]:=nr;
          h[nr]:=p^.v;
          percolate(nr,nr);
        end else begin
          percolate(nr,poz[p^.v]);
        end;
      end;
      p:=p^.next;
    end;

  end;

  for i:=2 to n do if d[i]<>64000 then write(d[i],' ') else write(0,' ');

  close(input);
  close(output);
end.