program dijkstra;
 const nmax=50010;
        inf=1 shl 30;
  type lista=^celula;
       celula=record
         info:longint;
         cost:longint;
         pred:lista;
         end;
  var a:array[0..nmax] of lista;
      viz,h,d:array[0..nmax] of longint;
      n,m,i,x,y,z:longint;
      r:lista;
      buf1,buf2:array[1..1 shl 16] of char;


  procedure swap(var a,b:longint);
   var aux:longint;
  begin
   aux:=a;
   a:=b;
   b:=aux;
  end;


  procedure heapdown(m,k:longint);
   var s:longint;
  begin
    repeat
      s:=0;
      if 2*k<=m then
        begin
         s:=2*k;
         if (2*k+1<=m)and(d[h[2*k+1]]<d[h[s]])
          then s:=2*k+1;
        if d[h[k]]<d[h[s]] then s:=0;
        end;
      if s<>0 then
        begin
          swap(h[k],h[s]);
          k:=s;
        end;
      until s=0;
  end;

  procedure heapup(m,k:longint);
   var key:longint;
  begin
   key:=h[k];
   while (k>1)and(d[h[k div 2]]>d[h[k]])do
     begin
       h[k]:=h[k div 2];
       k:=k div 2;
     end;
   h[k]:=key;
 end;

 procedure delete(var m:longint; k:longint);
  begin
    h[k]:=h[m];
    dec(m);
    if (k>1)and(d[h[k div 2]]>d[h[k]])
     then heapup(m,k)
     else heapdown(m,k);
  end;

  procedure insert(var m:longint; k:longint);
   begin
     inc(m);
     h[m]:=k;
     heapup(m,m);
   end;



  begin
    assign(input,'dijkstra.in');
    assign(output,'dijkstra.out');
    reset(input);
    rewrite(output);
    settextbuf(input,buf1);
    settextbuf(output,buf2);
    readln(n,m);
    for i:=1 to m do
      begin
        readln(x,y,z);
        new(r);
        r^.info:=y;
        r^.cost:=z;
        r^.pred:=a[x];
        a[x]:=r;
      end;

    m:=1;
    h[1]:=1;
    for i:=1 to n  do d[i]:=inf;
    d[1]:=0;
    viz[1]:=1;
    while m>0 do
      begin
       r:=a[h[1]];
       while r<>nil do
         begin
           if r^.cost+d[h[1]]<d[r^.info]
             then d[r^.info]:=r^.cost+d[h[1]];
           if viz[r^.info]=0 then
             begin
               viz[r^.info]:=1;
               insert(m,r^.info);
             end;
           r:=r^.pred;
         end;
       delete(m,1);
       end;
    for i:=2 to n do
      if d[i]=inf then
       write(0,' ') else
         write(d[i],' ');
    close(output);
  end.