#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
int ls,ld;
int q[Nmax];
double q1[Nmax];
double 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[0]=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]]=1;
			  }
           }
           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;
}