type adresa=^nod;
     nod= record
          inf,cost:longint;
          adr:adresa;
          end;
var n,m,a,b,c,i,min,k,j:longint;
    vc:array[1..50001]of adresa;
    viz:array[1..50001]of byte;
    d:array[1..50001]of longint;
    q,p:adresa;

begin
assign(input,'dijkstra.in');
reset(input);
read(n,m);
for i:=1 to n do
vc[i]:=nil;
for i:=1 to m do
begin
     read(a,b,c);
     new(q);
     q^.inf:=b;
     q^.cost:=c;
     q^.adr:=vc[a];
     vc[a]:=q;
end;
close(input);
for i:=2 to n do
d[i]:=maxlongint;
for i:=1 to n do
begin
     min:=maxlongint;
     for j:=1 to n do
         if (d[j]<min)and(viz[j]=0)then
         begin
              min:=d[i];
              k:=j;
         end;
     p:=vc[k];
     viz[k]:=1;
     while (p<>nil) do
     begin
          if(viz[p^.inf]=0)and(p^.cost+d[k]<d[p^.inf])then
          d[p^.inf]:=p^.cost+d[k];
          p:=p^.adr;
     end;
end;
assign(output,'dijkstra.out');
rewrite(output);
for i:=2 to n do
    if(d[i]=maxlongint)then
    write('0',' ')
    else
    write(d[i],' ');
close(output);
end.