#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

#define maxN 1505
#define PB push_back
#define MKP make_pair
#define inf (1 << 30)
#define MOD 104659
#define eps 1e-9

int dp[maxN];
double cost[maxN];
bool cont[maxN];
vector <pair <int, double> > list[maxN];
queue <int> Q;


int main()
{
	freopen ("dmin.in", "r", stdin);
	freopen ("dmin.out", "w", stdout);
	
	int N, M;
	
	scanf ("%d %d", &N, &M);
	
	while (M --)
	{
		int a, b, c;
		
		scanf ("%d %d %d", &a, &b, &c);
		
		list[a].PB ( MKP (b, log ((double) c)) );
		list[b].PB ( MKP (a, log ((double) c)) );
	}
	
	for (int i = 2; i <= N; ++ i) cost[i] = inf;
	
	Q.push (1);
	cont[1] = true;
	dp[1] = 1;
	
	while (! Q.empty ())
	{
		int nod = Q.front();
		Q.pop();
		
		cont[nod] = false;
		
		for (unsigned int i = 0; i < list[nod].size(); ++ i)
		{
			int nod2 = list[nod][i].first;
			double cost2 = list[nod][i].second;
			double costt = cost[nod] + cost2;
			
			if ((costt - cost[nod2]) > eps) continue;
			
			if (fabs (cost[nod2] - costt) <= eps)
			{
				dp[nod2] += dp[nod];
				if (dp[nod2] > MOD) dp[nod2] %= MOD;
				continue;
			}
			else dp[nod2] = dp[nod];
			
			cost[nod2] = costt;
			
			if (cont[nod2]) continue;
			
			Q.push (nod2);
			cont[nod2] = true;
		}
	}
	
	for (int i = 2; i <= N; ++ i) printf ("%d ", dp[i]);
	
	return 0;
}