type edge=record
       v1,v2,c:word;
     end;

var i,m,n,min,j:longint;
    nr:word;
    h,poz,d:array[0..50004] of word;
    e:array[0..250004] of edge;

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);
  assign(output,'dijkstra.out');
  rewrite(output);
  readln(n,m);
  for i:=1 to m do with e[i] do readln(v1,v2,c);

  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);
    for j:=1 to m do if e[j].v1=min then begin
      if d[e[j].v2]>d[e[j].v1]+e[j].c then begin
        d[e[j].v2]:=d[e[j].v1]+e[j].c;
        if poz[e[j].v2]=0 then begin
          inc(nr);
          poz[e[j].v2]:=nr;
          h[nr]:=e[j].v2;
          percolate(nr,nr);
        end else begin
          percolate(nr,poz[e[j].v2]);
        end;
      end;
    end;

  end;

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

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