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

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

const int MOD = 104659;

void dijkstra(int n, vector<vector<pair<int, double>>> &graf, vector<double> &dist, vector<int> &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<int> ans;

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

	graf.resize(n + 1);

	int x, y;
	long long z;

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

		double cost = log((double)z);

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

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

	dijkstra(n, graf, dist, ans);

	for (int i = 2; i <= n; i++){
		if (ans[i] == LLONG_MAX) {
			fout << "0";
		} else {
			fout << ans[i];
		}

		fout << ' ';
	}

	fout << '\n';

	return 0;
}