#include <bits/stdc++.h>
#define MOD 104659
using namespace std;

ifstream fin("dmin.in");
ofstream fout("dmin.out");

const double INF = 1e9;
const double EPS = 1e-9;

int n, m;
vector <pair<int, int> > a[1505];
bitset <1505> viz;
double dp[1505];
int sol[1505];
priority_queue <pair<double, int> > q;
double dabs(double x)
{
	return x > 0 ? x : -x;
}
int main()
{
	int x, y, i;
	double c, cost;
	fin >> n >> m;
	for (i = 1; i <= m; i++)
	{
		fin >> x >> y >> c;
		c = log2(c);
		a[x].push_back({ c, y });
		a[y].push_back({ c, x });
	}

	for (i = 1; i <= n; i++)
		dp[i] = INF;

	q.push({ 0, 1 });
	sol[1] = 1;
	dp[1] = 0;
	while (!q.empty())
	{
		x = q.top().second;
		cost = -q.top().first;
		q.pop();

			for (auto w : a[x])
			{
				if (dp[w.second] - (cost + w.first) > EPS)
				{
					dp[w.second] = cost + w.first;
					sol[w.second] = sol[x];
					q.push({ -dp[w.second], w.second });
				}
				else if (dabs(cost + w.first - dp[w.second]) < EPS)
					sol[w.second] = (sol[w.second] + sol[x]) % MOD;
			}
		
	}
	
	for (i = 2; i <= n; i++)
		fout << sol[i] << " ";


	return 0;
}