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

const int kMaxN = 1505, kMod = 104659;
const double kEps = 0.000001, kInf = 2000000000.69;

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

int N, M, nr[kMaxN];
double dist[kMaxN];
vector<pair<int, double>> G[kMaxN];

bool Equal(double a, double b) {
	return abs(a - b) <= kEps;
}
bool Less(double a, double b) {
	return a + kEps < b;
}

struct HeapMember {
	int node;
	double cost;
	HeapMember(int n, double c) {
		node = n;
		cost = c;
	}
	bool operator<(const HeapMember &other) const {
		return Less(other.cost, cost);
	}
};
priority_queue<HeapMember> pq;

int main() {
	fin >> N >> M;
	while (M--) {
		int x, y;
		double c;
		fin >> x >> y >> c;
		c = log(c);
		G[x].push_back(make_pair(y, c));
		G[y].push_back(make_pair(x, c));
	}
	for (int i = 2; i <= N; ++i)
		dist[i] = kInf;
	pq.push(HeapMember(1, 0.0));
	nr[1] = 1;
	while (!pq.empty()) {
		int node = pq.top().node;
		double cost = pq.top().cost;
		pq.pop();
		if (Less(dist[node], cost))
			continue;
		for (auto it : G[node]) {
			double new_cost = dist[node] + it.second;
			if (Equal(new_cost, dist[it.first])) {
				nr[it.first] = (nr[it.first] + nr[node]) % kMod;
			} else if (Less(new_cost, dist[it.first])) {
				dist[it.first] = new_cost;
				nr[it.first] = nr[node];
				pq.push(HeapMember(it.first, new_cost));
			}
		}
	}
	for (int i = 2; i <= N; ++i)
		fout << nr[i] << " ";
	return 0;
}