using namespace std;
#include <cstdio>
#include <vector>
#include <queue>
#define pb push_back
#include <cmath>
#define maxn 1501
#define eps 0.0000000000001
#define mod 104659

double a[maxn][maxn];
double d[maxn];
int dp[maxn];
vector<int>x[maxn];
int n;

void read()
{
	int m, p, q, c;
	freopen("dmin.in","r",stdin);
	scanf("%d %d\n", &n, &m);

	while(m--)
	{
		scanf("%d %d %d\n", &p, &q, &c);
		x[p].pb(q);
		x[q].pb(p);
		a[p][q]=a[q][p]=(double) log((double)c);
	}
}

void BF()
{
	queue<int>Q;
	//memset(d, 0x3f3f3f3f,sizeof(d));
	for(int i=0;i<=n;++i) d[i]=10000000;
	d[1]=0;
	int u,i;
	vector<int>::iterator it;
	Q.push(1);
	
	while(!Q.empty())
	{
		u=Q.front();
		Q.pop();
		
		for(it=x[u].begin();it!=x[u].end();++it)
			//if(d[u] + a[u][*it] < d[*it])
			if(d[*it]-d[u]-a[u][*it]>eps)
				Q.push(*it),
				d[*it]=d[u]+a[u][*it];
		
	}
	
}
	
void solve()
{
	memset(dp, 0, sizeof(dp));
	dp[1]=1;
	queue<int>Q;
	int u, i;
	vector<int>::iterator it,jt;
	
	Q.push(1);
	bool use[maxn];
	memset(use, 0,sizeof(use));
	use[1]=1;
	
	
	
	while(!Q.empty())
	{
		u=Q.front();
		Q.pop();
		
		for(it=x[u].begin();it!=x[u].end();++it)
			if(!use[*it])
			{
				Q.push(*it);
				use[*it]=1;
			//	if(d[u]+a[u][*it]==d[*it])
				
				for(jt=x[*it].begin();jt!=x[*it].end();++jt)
					
				if(fabs((d[*jt]+a[*jt][*it])-d[*it])<eps)
					dp[*it]+=dp[u], dp[*it]%=mod;
			
				//printf("(%d %d)  ", u, *it);
				//printf("%lf %lf %lf\n", d[u], a[u][*it], d[*it]);
			}
		
		
	}
	
	freopen("dmin.out","w",stdout);
	for(i=2;i<=n;++i)printf("%d ", dp[i]);
	
}
int main()
{
	read();
	BF();
	solve();
	
	return 0;
}