#include <fstream>
#include <queue>
#include <vector>

using namespace std;

struct Nod
{
	long long cost = (1LL << 60);
	vector<pair<int, int>> vecini;
};

typedef vector<Nod> Graf;
typedef pair<int, long> Pereche;

const int kMod = 104659;

void AflaDistante(Graf &g)
{
	auto cmp = [](const Pereche &a, const Pereche &b) -> bool { return a.second > b.second; };
	priority_queue<Pereche, vector<Pereche>, decltype(cmp)> coada(cmp);

	g[1].cost = 1;
	coada.push({ 1, 1 });

	while (!coada.empty()) {
		int nod = coada.top().first;
		long long cost = coada.top().second;
		coada.pop();

		if (cost != g[nod].cost) continue;

		for (auto &muchie : g[nod].vecini) {
			int vecin = muchie.first;
			long long cost_nou = cost * muchie.second;
			if (cost_nou < g[vecin].cost) {
				g[vecin].cost = cost_nou;
				coada.push({ vecin, cost_nou });
			}
		}
	}
}

vector<int> AflaModuri(const Graf &g)
{
	vector<int> moduri(g.size(), 0);
	queue<int> coada;
	vector<bool> in_coada(g.size(), false);

	coada.push(1);
	moduri[1] = 1;
	in_coada[1] = true;

	while (!coada.empty()) {
		int nod = coada.front();
		coada.pop();

		for (auto &muchie : g[nod].vecini) {
			int vecin = muchie.first;			
			if (g[vecin].cost == g[nod].cost * muchie.second && g[vecin].cost > g[nod].cost) {
				moduri[vecin] += moduri[nod];
				moduri[vecin] %= kMod;
				if (!in_coada[vecin]) {
					coada.push(vecin);
					in_coada[vecin] = true;
				}
			}
		}
	}
	return moduri;
}

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

	int n, m;
	fin >> n >> m;

	Graf graf(n + 1);
	while (m--) {
		int x, y, c;
		fin >> x >> y >> c;
		graf[x].vecini.push_back({ y, c });
		graf[y].vecini.push_back({ x, c });
	}

	AflaDistante(graf);

	auto raspuns = AflaModuri(graf);
	for (int i = 2; i < raspuns.size(); ++i)
		fout << raspuns[i] << " ";

	return 0;
}