#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>

using namespace std;

typedef pair<int, double> pid;

#define MOD 104659

int N, M;
vector<pid> G[1501];

double dist[1501];
int cnt[1501];
bool gata[1501];

void dijkstra() {
	for (int i(1); i <= N; ++i)
		dist[i] = 1 << 30;

	dist[1] = 0;
	cnt[1] = 1;

	for (int z(1); z < N; ++z) {
		int u = -1;
		for (int i(1); i <= N; ++i)
			if (!gata[i])
				if ((u == -1) || (dist[i] < dist[u]))
					u = i;
		//cout << "Sunt la " << u << " (" << dist[u] << " " << cnt[u] << ")" << endl;

		for (vector<pid>::iterator v = G[u].begin(); v != G[u].end(); ++v)
			if (!gata[v->first])
				if (dist[u] + v->second < dist[v->first]) {
					cnt[v->first] = cnt[u];
					dist[v->first] = dist[u] + v->second;
				} else if (abs(dist[u] + v->second - dist[v->first]) <= 1e-10) {
					cnt[v->first] = (cnt[v->first] + cnt[u]) % MOD;
				}

		gata[u] = true;
	}
}

int main(int argc, char *argv[]) {
	FILE *fi = fopen("dmin.in", "r");
	fscanf(fi, "%d %d", &N, &M);
	int u, v, w;
	for (int i(0); i < M; ++i) {
		fscanf(fi, "%d %d %d", &u, &v, &w);
		G[u].push_back(make_pair(v, log(w)));
		G[v].push_back(make_pair(u, log(w)));
	}
	fclose(fi);

	dijkstra();

	FILE *fo = fopen("dmin.out", "w");
	for (int i(2); i <= N; ++i)
		fprintf(fo, "%d ", cnt[i]);
	fprintf(fo, "\n");
	fclose(fo);

	return 0;
}