//#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <fstream>
#include <cmath>
#include <cfloat>
using namespace std;

ifstream cin("dmin.in");
ofstream cout("dmin.out");

const int MOD = 104659;

void dijkstra(int n, vector<vector<pair<int, double>>> &graf, vector<double> &dist, vector<long long> &ans)
{
	priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> pq;

	dist[1] = 0;
	ans[1] = 1;
	pq.push({0, 1});

	while (!pq.empty()){
		double d = pq.top().first;
		int nod = pq.top().second;
		pq.pop();

		if (d != dist[nod]){
			continue;
		}

		for (auto grafi : graf[nod]){
			int vecin = grafi.first;
			double cost = grafi.second;

			if (dist[vecin] > dist[nod] + cost + 1e-9){
				dist[vecin] = dist[nod] + cost;
				ans[vecin] = ans[nod];

				pq.push({dist[vecin], vecin});
			}
			else if (abs(dist[vecin] - (dist[nod] + cost)) <= 1e-9){
				ans[vecin] = (ans[vecin] + ans[nod]) % MOD;
			}
		}
	}
}

vector<vector<pair<int, double>>> graf;
vector<double> dist;
vector<long long> ans;

int main()
{
	int n, m;
	cin >> n >> m;

	graf.resize(n + 1);

	int x, y;
	long long z;

	for (int i = 1; i <= m; i++){
		cin >> x >> y >> z;

		double cost = log((double)z);

		graf[x].push_back({y, cost});
		graf[y].push_back({x, cost});
	}

	dist.resize(n + 1, DBL_MAX);
	ans.resize(n + 1, 0);

	dijkstra(n, graf, dist, ans);

	for (int i = 2; i <= n; i++){
		cout << ans[i] << ' ';
	}

	cout << '\n';

	return 0;
}