const inf=2000000000;
const nmax=50001;
type lista=^elem;
     elem=record
         v,c:longint;
         adu:lista;
         end;

var d,viz:array[1..nmax] of longint;
a:array[1..nmax] of lista;
c:array[1..4*nmax]of longint;
q:lista;
f,g:text;
ct,i,j,x,pc,uc,y,n,m:longint;
begin
assign(f,'dijkstra.in');
reset(f);
assign(g,'dijkstra.out');
rewrite(g);
readln(f,n,m);
for i:=1 to m do
   begin
     readln(f,x,y,ct);
     new(q);
     q^.c:=ct;
     q^.v:=y;
     q^.adu:=a[x];
     a[x]:=q;
     end;

for i:=2 to n do
   d[i]:=inf;
pc:=1;
uc:=1;
c[pc]:=1;
viz[1]:=1;
while pc<=uc do
     begin
        q:=a[c[pc]];
        while q<>NIL do
            begin
               if (q^.c+d[c[pc]])<d[q^.v] then
                   begin
                     d[q^.v]:=q^.c+d[c[pc]];
                     if viz[q^.v]=0 then
                          begin
                            uc:=uc+1;
                            c[uc]:=q^.v;
                            viz[q^.v]:=1;
                            end;
                     end;
               q:=q^.adu;
            end;
        viz[c[pc]]:=0;
        pc:=pc+1;
     end;
for i:=1 to n do
    if d[i]=inf then d[i]:=0;
for i:=2 to n do
   write(g,d[i],' ');
close(g);
end.