#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;

int main()
{
	int x, y, i;
	double c;
	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;
		q.pop();
		if (viz[x] == 0)
		{	
			viz[x] = 1;
			for (auto w : a[x])
			{
				if (dp[w.second] > dp[x] + w.first + EPS)
				{
					dp[w.second] = dp[x] + w.first;
					sol[w.second] = sol[x];
					q.push({ -dp[w.second], w.second });
				}
				else if (dp[x] + 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;
}