program dijkstra;   
const INF:longint=1000*250000;   
type  
    pnod=^nod;   
    nod = record  
     vecin:integer;   
     cost:longint;   
     urm:pnod;   
    end;   
var list:array[1..50000]of pnod;
    drum:array[1..50000]of longint;
    c:array[0..60000]of integer;
    n,m:integer;
procedure insert(a,b,c:integer);
var aux:pnod;
begin
 aux:=new(pnod);
 aux^.vecin:=b;
 aux^.cost:=c;
 aux^.urm:=list[a];
 list[a]:=aux;
end;   
  
procedure citire;   
var ii,jj,cst:integer;   
    i:integer;   
    f:text;   
begin  
assign(f,'dijkstra.in');reset(f);   
readln(f,n,m);   
for i:=1 to m do begin  
     readln(f,ii,jj,cst);   
     insert(ii,jj,cst);   
    end;   
close(f);   
end;   
  
procedure Ford;
const Kmod:longint=60000;
var sursa,next,cst:integer;
    si,fi:longint;
    i,j:longint;
    it:Pnod;
begin  
  it:=new(Pnod);   
  for i:=1 to n do drum[i]:=INF;   
  drum[1]:=0;   
  si:=1;fi:=1;  {start coada, sfarsit coada}  
  c[si]:=1;   
  while si<=fi do begin  
    sursa:=c[si mod Kmod];
    si:=si+1;   
    it:=list[sursa];   
    while (it <> NIL)do begin  
           next:=it^.vecin;   
           cst:=it^.cost;   
           it:=it^.urm;   
           if drum[next]>drum[sursa]+cst then begin  
  
               fi:=fi+1;   
               c[fi mod KMod]:=next;
               drum[next]:=drum[sursa]+cst;   
              end;   
         end;   
  end;   
  
end;   
  
procedure afis;   
var f:text;   
    i:integer;   
begin  
assign(f,'dijkstra.out');rewrite(f);   
for i:=2 to n do  
    if drum[i]=INF then write(f,'0 ')   
    else write(f,drum[i],' ');   
close(f);   
end;   
  
begin  
citire;   
FORD;   
afis;   
end.