#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#define pb push_back
#define maxn 1505
#define eps 0.00000000001
#include <string>
#define mod 104659
using namespace std;

struct nod { double c; int x; nod(){}; nod(int a, double b){ x=a; c=b;};};

vector<vector<nod> >a;
int n, m;
double d[maxn];
int sol[maxn];

void citire()
{
	int p, q,c;double C;
	freopen("dmin.in", "r", stdin);
	scanf("%d %d\n", &n, &m);
	a.resize(n+1);
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d %d\n", &p, &q, &c);
		C=(double) log(c);
		a[p].pb(nod(q, C));
		a[q].pb(nod(p, C));
	}
}
bool operator<(const nod &a, const nod & b)
{
	if(b.c-a.c>eps) return 1;
	return 0;
}
double sgn(double a)
{
	if(a<0) return -a;
	return a;
}
void dijkstra()
{
	int i, j, nh=n, u;
	bool viz[maxn];
	priority_queue<nod> Q;
	vector<nod> ::iterator it;
	Q.push(nod(1, 0));
	for(i=1;i<=n;i++) d[i]=2000000000;
	memset(viz, 0,sizeof(viz));
	d[1]=0;
	sol[1]=1;
	while(!Q.empty() && nh)
	{
		u=Q.top().x;
		Q.pop();
		if(viz[u]) continue;
		viz[u]=1;
		--nh;
		for(it=a[u].begin();it!=a[u].end();++it)
			if(((d[it->x] - (d[u]+it->c))) >eps)
			{		
				d[it->x]=d[u]+it->c;
				Q.push(nod(it->x, d[it->x]));
				//sol[it->x]=sol[u];
				//sol[it->x]%=mod;
			}
			
			//else
		/*	if(fabs((d[it->x] - (d[u]+it->c))) <=eps )
			{
				sol[it->x]+=sol[u];
				sol[it->x]%=mod;
			}
			*/
			
			/*
		for(it=a[u].begin();it!=a[u].end();++it)
			if((d[it->x] - (d[u]+it->c)) <=eps && it->x !=u && !viz[it->x])
			{
				sol[it->x]+=sol[u];
				sol[it->x]%=mod;
*/			
			
	}
	//for(i=1;i<=n;i++) printf("%f ", exp(d[i]));
	//printf("\n");
	
}

int memo(int nd)
{
	//printf("%d\n", nd);
	
	if(nd==1) return 1;
	if(sol[nd]) return sol[nd];
	
	for(vector<nod>::iterator it=a[nd].begin();it!=a[nd].end();++it)
		if((fabs((d[it->x]+it->c)-d[nd])) <=eps )
		{
			//printf("%lf %lf %lf\n", d[nd], d[it->x]+it->c,(d[nd] -(d[it->x]+it->c)));
			sol[nd]+=memo(it->x), sol[nd]%=mod;
		}
	return sol[nd];
}

void solve()
{
	int Q[maxn], p=1, q=1, viz[maxn];
	memset(Q, 0, sizeof(Q));
	memset(viz, 0, sizeof(viz));
	Q[1]=1;
	sol[1]=1;
	viz[1]=1;
	int u, i;
	vector<nod>::iterator it, jt;
	
	while(p<=q)
	{
		u=Q[p++];
		
		for(it=a[u].begin();it!=a[u].end();++it)
			if(!viz[it->x])
			{
				viz[it->x]=1;
				i=it->x;
				for(jt=a[i].begin();jt!=a[i].end();++jt)
					if(viz[jt->x] && ((d[jt->x] - (d[i]+jt->c)) <=eps))
					{
						sol[it->x]+=sol[jt->x];
						sol[it->x]%=mod;
					}
			}
	}
	//	for(i=1;i<=n;i++) printf("%d ", sol[i]);
}
int main()
{
	citire();
	dijkstra();
	
	for(int i=n;i>1;i--) memo(i);
	//memo(n);
	freopen("dmin.out", "w", stdout);
	for(int i=2;i<=n;i++) printf("%d ", sol[i]);
//solve();
	return 0;
}