#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <functional>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <bitset>
#include <stack>
#define MOD 1000000007
#define NMAX 2000
#define MMAX 5005
#define INF 0x3f3f3f
#define mp make_pair

using namespace std;

FILE *fin = freopen("dmin.in", "r", stdin);
FILE *fout = freopen("dmin.out", "w", stdout);

typedef pair<int, int> pii;

vector<pair<double, int> > v[NMAX];
bool viz[NMAX];
double dist[NMAX];
int nr[NMAX];

const double EPS = 1e-10;

int main() {
	int n, m, i, x, y, c;
	double c1;

	scanf("%d%d", &n, &m);

	for (i = 0; i < m; ++i) {
		scanf("%d%d%d", &x, &y, &c);

		c1 = log2(1.0*c);

		v[x].push_back({ c1, y });
		v[y].push_back({ c1, x });
	}

	priority_queue < pair<double, int>, vector<pair<double, int> >, greater<pair<double, int> > > pq;
	pq.push({ 0.0, 1 });
	for (i = 2; i <= n; ++i)
		dist[i] = 1000000;

	nr[1] = 1;
	while (!pq.empty()) {
		x = pq.top().second;
		pq.pop();

		if (!viz[x]) {
			viz[x] = true;

			for (i = 0; i < v[x].size(); ++i) {
				y = v[x][i].second;
				c1 = v[x][i].first;

				if (dist[y] - (dist[x] + c1) >= EPS) {
					dist[y] = dist[x] + c1;
					nr[y] = nr[x];
					pq.push({ dist[y], y });
				}
				else if (abs(dist[y] - (dist[x] + c1)) < EPS) {
					nr[y] += nr[x];
					nr[y] %= 104659;
					pq.push({ dist[y], y });
				}
			}
		}
	}

	for (i = 2; i <= n; ++i)
		printf("%d ", nr[i]);

	return 0;
}