type Lista=^Element;
     Element=record
              nr:longint;
              cost:integer;
              leg:Lista;
             end;

var n,m,s:longint;
    vecini:array[1..50000] of record
                                first,last:Lista;
                               end;
    dmin:array[1..50000] of longint;

procedure Citeste;
var f:text;
    i:longint;
    l,test:Lista;
    a,b:longint;
    c:integer;
 begin
  assign(f,'dijkstra.in');
  reset(f);
  readln(f,n,m);
  for i:=1 to n do
   begin
    New(l);
    l^.nr:=0;
    l^.leg:=nil;
    vecini[i].first:=l;
    vecini[i].last:=l;
   end;
  for i:=1 to m do
   begin
    readln(f,a,b,c);
    New(l);
    l^.nr:=b;
    l^.cost:=c;
    l^.leg:=nil;
    vecini[a].last^.leg:=l;
    vecini[a].last:=l;
   end;
  close(f);
 end;

procedure Parcurge;
 const SizeC=350000;
 var i,j,nod,vecin,inC,sfC,nrC:longint;
     C:array[1..SizeC] of longint;
     d:array[1..sizeC] of longint;
     l:Lista;
 begin
  for i:=1 to n do dmin[i]:=maxlongint;
  inC:=1;sfC:=1;nrC:=1;
  c[1]:=1;d[1]:=0;
  while (inC<=sfC) or (nrC>1) do
   begin
    nod:=C[inC];
    if d[inC]<dmin[nod] then
    begin
     dmin[nod]:=d[inC];
     l:=vecini[nod].first;
     repeat
      begin
       vecin:=l^.nr;
       if vecin<>0 then
         if dmin[nod]+l^.cost<dmin[vecin] then
          begin
           nrC:=nrC+1;
           sfC:=sfC+1;
           if sfC>sizeC then sfC:=1;
           C[sfC]:=vecin;
           d[sfC]:=dmin[nod]+l^.cost;
          end;
       l:=l^.leg;
      end;
     until l=nil;
   end;
   nrC:=nrC-1;
   inC:=inC+1;
   if inC>sizeC then inC:=1;
  end;
 end;

procedure Scrie;
var f:text;
    i:longint;
begin
 assign(f,'dijkstra.out');
 rewrite(f);
 for i:=2 to n do
  begin
   if dmin[i]=maxlongint then write(f,'0 ')
   else write(f,dmin[i],' ');
  end;
 close(f);
end;

begin
Citeste;
Parcurge;
Scrie;
end.