program dijkstra;
const INF:integer=30000;
type
    pnod=^nod;
    nod = record
     vecin:integer;
     cost:longint;
     urm:pnod;
    end;
var list:array[1..5000]of pnod;
    drum:array[1..5000]of longint;
    c:array[1..10000]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;
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];
    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]:=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.