#include <cstdio>
#include <cmath>
#include <vector>

using namespace std;

#define file_in "dmin.in"
#define file_out "dmin.out"

#define Nmax 2501
#define Inf 0x3f3f3f3f
#define Mod 104659
#define pb push_back
#define eps 1e-10

int x,y,cc;
int n,m,ok,i,j;
int g[Nmax];//gradul
double d[Nmax];
int ls,ld;
int q[Nmax];
int q1[Nmax];
int q2[Nmax];

double l;

vector<int> v[Nmax];
vector<double> c[Nmax]; //costul logaritmat

int p[Nmax];//nr. de drumuri minime

void citire()
{
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d", &n,&m);
	for (i=1;i<=m;++i)
	{
		scanf("%d %d %d", &x,&y,&cc);
		//graf neorientat
		g[x]++;
		g[y]++;
		v[x].pb(y);
		v[y].pb(x);
		l=log10((double)cc);
		c[x].pb(l);
		c[y].pb(l);
		
	}
}

void solve()
{
	/*for (i=2;i<=n;++i)
		 if (d[i]==0)
			  d[i]=Inf;
	
    ok=0;
    while(!ok)
	{
		ok=1;
		for (i=1;i<=m;++i)
			 if (d[y[i]]>d[x[i]]*c[i] && d[x[i]]!=0)
				 d[y[i]]=d[x[i]]*c[i],ok=0;
			 else*/
			 /*if (d[y[i]]==d[x[i]]*c[i] && d[x[i]]!=0) 
				 //p[i]++;*/
	/*		 printf("%d\n", d[y[i]]);	 
	}*/

   /* for (i=2;i<=n;++i)
         printf("%d ",d[i]);*/
	
	for (i=1;i<=n;++i)
		 q2[i]=Inf;
	for (i=1;i<=n;++i)
		 p[i]=1;
	
	
	ls=0;
	ld=1;
	q[1]=q1[1]=q2[1]=1;
	while(ls<ld)
	{
		x=q[ls];
		for (i=0;i<g[x];++i)
		{
			if (q2[x]+c[x][i]<q2[v[x][i]] && fabs(q2[x]+c[x][i]-q2[v[x][i]])>eps)
			{
				p[v[x][i]]=p[x];
				q2[v[x][i]]=q2[x]+c[x][i];
                if (!q1[v[x][i]])
				{
					q[ld]=v[x][i];
					ld++;
					q1[v[x][i]]++;
				}
			}
			else
			if (fabs(q2[x]+c[x][i]-q2[v[x][i]])<eps)
            {
				p[v[x][i]]=(p[x]+p[v[x][i]])%Mod;
			}
		}
		q1[x]=0;
		ls++;
	}
}

void scrie()
{
	for (i=2;i<=n;++i)
		 printf("%d ", p[i]);
}

int main()
{
	citire();
	solve();
	scrie();
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}