//#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()) {
		int nod = pq.top().second;
		pq.pop();

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

			if (dist[vecin] > dist[nod] + cost) {

				dist[vecin] = dist[nod] + cost;
				ans[vecin] = ans[nod];

				pq.push({dist[vecin], vecin});

			} else if (dist[vecin] == dist[nod] + cost) {

				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++){
		if (dist[i] == DBL_MAX) {
			cout << "0";
		} else {
			cout << ans[i];
		}

		cout << ' ';
	}

	cout << '\n';

	return 0;
}