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

double EPSILON = 0.000001;
const int Inf = 1e9 + 1;
int n, m;
vector<pair<double, int>> a[1501];
double d[1501];
int nrways[1501];
const int MOD = 104659;

void read() {
	int x, y, i;
	double c;
	ifstream f("dmin.in");
	f >> n >> m;
	for (i = 1; i <= m; i++) {
		f >> x >> y >> c;
		a[x].emplace_back(log2(c), y);
		a[y].emplace_back(log2(c), x);
	}
	f.close();
}

priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> Q;
void dijkstra(int x) {
	pair<double, int> p, cur;
	int i;
	d[x] = 0;
	nrways[1] = 1;
	Q.push(make_pair(0, x));
	while (!Q.empty()) {
		p = Q.top();
		Q.pop();
		if (p.first != d[p.second]) continue;
		for (i = 0; i < a[p.second].size(); i++) {
			cur = a[p.second][i];
			if(d[p.second] + cur.first - d[cur.second] < -EPSILON) {
				d[cur.second] = d[p.second] + cur.first;
				Q.push(make_pair(d[cur.second], cur.second));
				nrways[cur.second] = nrways[p.second];
			}
			else if(abs(d[p.second] + cur.first - d[cur.second]) < EPSILON)
                nrways[cur.second] = (nrways[cur.second] + nrways[p.second]) % MOD;
		}
	}
}

void solve() {
	int i;
	for (i = 1; i <= n; i++)
		d[i] = Inf;
	dijkstra(1);
}

void output() {
	ofstream g("dmin.out");
	int i, j;
	for (i = 2; i <= n; i++)
		g << nrways[i] << ' ';
	g.close();
}

int main() {
	read();
	solve();
	output();
	return 0;
}