#include <cmath>
#include <cstdio>
using namespace std;

typedef long long int lli;
int const maxn=1500,maxm=2500,mod=104659;
double const eps=1e-8,inf=30*maxn;// log(10**9)<30
int N,M,E3[maxm][3],H[maxn],J[maxn],hs,I[maxn+1],Ji[maxn],C[maxn];
struct Edge{int to;double w;} A[2*maxm];
double D[maxn];

void pop_heap()
{	int t,r,c;
	--hs;t=H[0];H[0]=H[hs];J[H[0]]=0;H[hs]=t;
	r=0;c=(2*(r+1))-1;
	while(c<hs)
	{	if(((c+1)<hs)&&(D[H[c]]>D[H[c+1]]))
		{++c;}
		if(D[H[r]]>D[H[c]])
		{	t=H[r];H[r]=H[c];J[H[r]]=r;H[c]=t;J[H[c]]=c;
			r=c;c=(2*(r+1))-1;
		}
		else{c=hs;}
	}
}

void decrease_key(int i,double v)
{	int r,c,t;
	D[i]=v;c=J[i];
	while(0<c)
	{	r=(c-1)/2;
		if(D[H[c]]<D[H[r]])
		{	t=H[c];H[c]=H[r];J[H[c]]=c;H[r]=t;J[H[r]]=r;
			c=r;
		}
		else{c=0;}
	}
}

void update(int x,int y,double v)
{	if(fabs(v-D[y])<eps)
	{C[y]=(C[y]+C[x])%mod;}
	else
	{	if(v<D[y])
		{	if(inf==D[y]){H[hs]=y;J[y]=hs;++hs;}
			decrease_key(y,v);C[y]=C[x];
		}
	}
}

void dijkstra()
{	int x,y,i,t;
	double w;
	for(x=0;N>x;++x){D[x]=inf;}
	hs=0;C[0]=1;update(0,0,0.0);
	while(0<hs)
	{	pop_heap();x=H[hs];i=I[x];t=I[x+1];
		while(i<t)
		{	y=A[i].to;w=A[i].w;
			update(x,y,D[x]+w);
			++i;
		}
	}
}

int main()
{	freopen("dmin.in","r",stdin);
	freopen("dmin.out","w",stdout);
	scanf("%d %d",&N,&M);int i,x,y;double w;
	for(i=0;M>i;++i)
	{	scanf("%d %d %d",&E3[i][0],&E3[i][1],&E3[i][2]);
		--E3[i][0];--E3[i][1];
	}
	for(i=0;N>i;++i){I[i]=0;}
	for(i=0;M>i;++i)
	{	x=E3[i][0];y=E3[i][1];
		++I[x];++I[y];
	}
	x=I[0];I[0]=0;
	for(i=1;N>=i;++i)
	{y=I[i];I[i]=I[i-1]+x;x=y;}
	for(i=0;N>i;++i){Ji[i]=I[i];}
	for(i=0;M>i;++i)
	{	x=E3[i][0];y=E3[i][1];w=log(E3[i][2]);
		A[Ji[x]].to=y;A[Ji[x]++].w=w;
		A[Ji[y]].to=x;A[Ji[y]++].w=w;
	}
	if(1<N)
	{	dijkstra();
		printf("%d",C[1]);
		for(i=2;N>i;++i)
		{printf(" %d",C[i]);}
	}
	return 0;
}