#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <string>

using namespace std;

#define PB push_back
#define MKP make_pair
#define NM 1505
#define inf 1e10
#define eps 0.000000001
#define MOD 104659

double dmin[NM];
int w[NM], in[NM];

vector <pair<int, int> > G[NM];

double ab(double nr)
{
	if (nr >= 0) return nr;
	else return -nr;
}	

double eq(double a, double b)
{
	if (ab(a-b) < eps) return 1;
	return 0;
}	

int main()
{
	freopen ("dmin.in", "r", stdin);
	freopen ("dmin.out", "w", stdout);
	
	int N, M;
	
	scanf ("%d %d", &N, &M);
	
	for (int i = 1; i <= M; ++i)
	{
		int a, b, c;
		scanf ("%d %d %d", &a, &b, &c);
		
		G[a].PB(MKP(b, c));
		G[b].PB(MKP(a, c));
	}	
	
	for (int i = 1; i <= N; ++i) dmin[i] = inf;
	
	dmin[1] = 0;
	w[1] = 1;
	
	for (int i = 2; i <= N; ++i)
	{	
		double best = inf;
		int nbest;
		
		for (int j = 1; j <= N; ++j) if (!in[j] && best > dmin[j])
		{
			best = dmin[j];
			nbest = j;
		}	
		
		in[nbest] = 1;
		
		for (int j = 0; j < G[nbest].size(); ++j)
		{
			int nod = G[nbest][j].first;
			if (in[nod]) continue;
			double cost = log((double)G[nbest][j].second);
			if (eq(dmin[nbest] + cost, dmin[nod])) w[nod] = (w[nod] + w[nbest]) % MOD;
			else if (dmin[nbest] + cost < dmin[nod])
			{
				dmin[nod] = dmin[nbest] + cost;
				w[nod] = w[nbest];
			}	
		}	
	}
 	
	for (int i = 2; i <= N; ++i) printf ("%d ", w[i]);
	
	return 0;
}