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

var poz,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,'dmin.in');
reset(f);
assign(g,'dmin.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
   begin
   d[i]:=inf;
   poz[i]:=1;
   end;
poz[1]:=1;
d[1]:=1;
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
                     poz[q^.v]:=poz[c[pc]];
                     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
                     else if (q^.c*d[c[pc]])=d[q^.v] then poz[q^.v]:=poz[q^.v]+poz[c[pc]];
               q:=q^.adu;
            end;
        viz[c[pc]]:=0;
        pc:=pc+1;
     end;

for i:=2 to n do
   begin
   write(g,(poz[i]mod 104659),' ');
   end;
close(g);
end.