#include<stdio.h>
#include<vector>
#include<cmath>
#include<queue>
#define nmax 2003
#define MOD 104659

using namespace std;

typedef pair<double, int> p;

priority_queue<p, vector<p>, greater<p> > h;
vector<p> g[nmax];
int n,m,i,j,a,b, nr[nmax], inf=2<<20, viz[nmax];
double drum[nmax], d;


int main()
{
	freopen("dmin.in", "r", stdin);
	freopen("dmin.out", "w", stdout);
	scanf("%d %d", &n, &m);
	for(i=1;i<=m;i++)
	{
		scanf("%d %d %lf", &a, &b, &d);
		g[a].push_back(make_pair(log10(d),b));
		g[b].push_back(make_pair(log10(d),a));
	}
	vector<p>::iterator it;
	for(i=1;i<=n;i++)
		drum[i]=inf;
	drum[1]=1;
	nr[1]=1;
	h.push(make_pair(1,1));
	while(!h.empty())
	{
		while(!h.empty()&&viz[h.top().second]==1)
			h.pop();
		if(h.empty())
			break;
		d=h.top().first;
		a=h.top().second;
		h.pop();
		viz[a]=1;
		for(it=g[a].begin();it!=g[a].end();it++)
			if(fabs(it->first+d-drum[it->second])<0.00000001)
				nr[it->second]=(nr[it->second]+nr[a])%MOD;
			else if(it->first+d<drum[it->second])
			{
				drum[it->second]=it->first+d;
				nr[it->second]=nr[a];
				h.push(make_pair(drum[it->second], it->second));
			}
	}
	for(i=2;i<=n;i++)
		printf("%d ", nr[i]);
	printf("\n");
	return 0;
}