#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>

const int kMaxDim = 1505;
const int kModulo = 104659;
const double eps = 1e-8;
const double inf = 1e10;

inline double Abs(const double& a) {
	return (a > 0 ? a : -a);
}

inline int Compare(const double& a, const double& b) {
	if (Abs(a - b) < eps)
		return 0;
	return (a < b ? -1 : 1);
}

struct Data {
	int node;
	double cost;
};

struct Functor {
	bool operator()(const Data& a, const Data& b) {
		return Compare(a.cost, b.cost) > 0;
	}
};

int nodeCount, edgeCount;
std::vector< Data > edges[kMaxDim];
double minDist[kMaxDim];
int minDistCount[kMaxDim];

std::priority_queue< Data, std::vector< Data >, Functor > heap;

int main() {
	std::ifstream inputFile("dmin.in");
	std::ofstream outputFile("dmin.out");

	inputFile >> nodeCount >> edgeCount;
	for (int i = 1; i <= edgeCount; ++i) {
		int first, second;
		double cost;
		inputFile >> first >> second >> cost;
		cost = log(cost);

		edges[first].push_back({second, cost});
		edges[second].push_back({first, cost});
	}

	for (int i = 2; i <= nodeCount; ++i)
		minDist[i] = inf;
	minDistCount[1] = 1;
	heap.push({1, 0});

	while (!heap.empty()) {
		while (!heap.empty() && Compare(minDist[heap.top().node], heap.top().cost) < 0)
			heap.pop();
		if (heap.empty())
			break;

		int node = heap.top().node;
		double cost = heap.top().cost;
		heap.pop();

		for (Data& edge : edges[node]) {
			if (Compare(minDist[edge.node], cost + edge.cost) > 0) {
				minDist[edge.node] = cost + edge.cost;
				minDistCount[edge.node] = minDistCount[node];
				heap.push({edge.node, minDist[edge.node]});
			}
			else if (Compare(minDist[edge.node], cost + edge.cost) == 0) {
				minDistCount[edge.node] += minDistCount[node];
				minDistCount[edge.node] %= kModulo;
			}
		}
	}

	for (int i = 2; i <= nodeCount; ++i)
		outputFile << minDistCount[i] << ' ';
	outputFile << '\n';

	inputFile.close();
	outputFile.close();

	return 0;
}

//Trust me, I'm the Doctor!