#include <bits/stdc++.h>

using namespace std;
ifstream r("dmin.in");
ofstream w("dmin.out");

const double eps = 1e-9;
const int mod=104659;
int n, m, viz[1503], sol[1503];
vector <pair<double, int> > a[1505];
double dp[1503];
priority_queue <pair<double, int> > q;
double dabs(double x)
{
	return x > 0 ? x : -x;
}
int main()
{
	int x, y;
	double c;
	r >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		r >> x >> y >> c;
		c = log2(c);
		a[x].push_back({ c, y });
		a[y].push_back({ c, x });
	}

	for (int i = 1; i <= n; i++){
		dp[i] = 1000000000;
	}
	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 it : a[x])
			{
				if (dp[it.second] - (dp[x] + it.first) > eps)
				{
					dp[it.second] = dp[x] + it.first;
					sol[it.second] = sol[x];
					q.push({ -dp[it.second], it.second });
				}
				else if (dabs(dp[x] + it.first - dp[it.second]) < eps){
					sol[it.second] = (sol[it.second] + sol[x]) % mod;
				}
			}
		}
	}

	for (int i = 2; i <= n; i++){
		w << sol[i] << " ";
	}
	return 0;
}