#include <fstream.h>
#define inf 10000
ifstream f("dmin.in");
ofstream g("dmin.out");
long t=0,n;
void dr(long vf1,long vf2,long co,long cost,long (*c)[100])
{
long i;
if (vf1==vf2&&co==cost) {t++;return;}
else
	for (i=1;i<=n;i++)
		if (c[vf1][i]!=inf&&i!=vf1)
			dr(i,vf2,co*c[vf1][i],cost,c);
}

int main()
{
long *cost,(*c)[100],*v,x,y,min,poz,co,m,i,j,ii,ij;
f>>n>>m;
v=new long[n+1];
cost=new long[n+1];
c=new long[100][100];
for (i=1;i<=n;i++)
	for (j=1;j<=n;j++)
		if (i!=j) c[i][j]=inf;
		else c[i][j]=0;
for (i=1;i<=m;i++)
		{
		f>>x>>y>>co;
		c[x][y]=co;
		}
x=1;
for (ii=2;ii<=n;ii++)
	{
	t=0;
	for (ij=1;ij<=n;ij++) v[ij]=cost[ij]=0;
	y=ii;
	v[1]=1;
	for (i=1;i<=n;i++)
		cost[i]=c[x][i];
	for (i=1;i<n;i++)
		{
		min=inf;
		for (j=1;j<=n;j++)
			if (!v[j]&&cost[j]<min)
				{
				min=cost[j];
				poz=j;
				}
		v[poz]=1;
		for (j=1;j<=n;j++)
			if (!v[j]&&cost[j]>cost[poz]*c[poz][j])
				cost[j]=cost[poz]*c[poz][j];
		}
		dr(x,y,1,cost[y],c);
		g<<t%104659<<" ";
//	g<<"\nCostul minim: "<<cost[y];
	}
return 0;
}