#include<cstdio>
#include<vector>
#include<queue>
#include<bitset>
#include<cmath>
using namespace std;

int n,m,i,x,y,drum[10000],MOD=104659,inf=987654321;
double d[10000],c,eps=0.0000000001;
queue<int> Q;
vector<pair<int,double> > V[10000];
bitset<10000> q;

void read(),solve();

int main()
{
	read();
	solve();
	
	return 0;
}

void read()
{
	freopen("dmin.in","r",stdin);
	freopen("dmin.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		int c;
		scanf("%d%d%d",&x,&y,&c);
		V[x].push_back(make_pair(y,log((double)c)));
		V[y].push_back(make_pair(x,log((double)c)));
	}
}

void solve()
{
	vector<pair<int,double> >::iterator it;
	for(i=1;i<=n;i++)d[i]=inf;
	drum[1]=1;d[1]=0;q[1]=1;Q.push(1);
	for(;Q.size();Q.pop())
	{
		x=Q.front();
		for(it=V[x].begin();it!=V[x].end();it++)
		{
			y=it->first;
			double c=it->second;
			if(fabs(d[y]-d[x]-c)<eps)drum[y]=(drum[y]+drum[x])%MOD;
		    else if(d[y]-d[x]-c>eps)
			{
				if(!q[y]){Q.push(y);q[y]=1;}
				d[y]=d[x]+c;
				drum[y]=drum[x];
			}
		}
		q[x]=0;
	}
	for(i=2;i<=n;i++)printf("%d ",drum[i]);
}