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

using namespace std;

typedef pair<int, int> p;

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


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 %d", &a, &b, &d);
		g[a].push_back(make_pair(d,b));
		g[b].push_back(make_pair(d,a));
	}
	vector<p>::iterator it;
	for(i=1;i<=n;i++)
		drum[i]=inf;
	drum[1]=0;
	nr[1]=1;
	h.push(make_pair(0,1));
	while(!h.empty())
	{
		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(d+it->first==drum[it->second])
				nr[it->second]=(nr[it->second]+nr[a])%MOD;
			else if(d+it->first<drum[it->second])
			{
				drum[it->second]=d+it->first;
				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;
}