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

ifstream cin("dmin.in");
ofstream cout("dmin.out"); 

const int INF = 1e9 + 999;
const int MOD = 104659;
const int MAX = 1502;
const double EPS = 1e-9;

struct Muchii {
	int nod;
	double cost;

	bool operator<(const Muchii& A) const {
		return cost - A.cost > EPS;
	}
};

priority_queue<Muchii> pq;
vector<Muchii> adj[MAX];
double dp[MAX];
int ans[MAX];
int n, m;

static inline void dj() {
	for(int i = 2; i <= n; i++)
		dp[i] = INF;

	ans[1] = 1;
	dp[1] = 0;
	pq.push({1, 0});
	int cur;
	double cost, C;
	while(!pq.empty()) {
		cur = pq.top().nod;
		cost = pq.top().cost;
		pq.pop();

		for(const Muchii &M : adj[cur]) {
			C = dp[cur] + M.cost;
			if(dp[M.nod] - C > EPS) {
				ans[M.nod] = ans[cur];

				dp[M.nod] = C;
				pq.push({M.nod, dp[M.nod]});
			} else if(abs(dp[M.nod] - C) < EPS)
				ans[M.nod] = ((long long)ans[M.nod] + ans[cur]) % MOD;
		}
	}
}

signed main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> m;

	int x, y;
	int c;
	while(m--) {
		cin >> x >> y >> c;
		double C = log2((double)c) * 10;
		adj[x].push_back({y, C});
		adj[y].push_back({x, C});
	}

	dj();

	for(int i = 2; i <= n; i++)
		cout << ans[i] << ' ';
	cout << '\n';
	return 0;
}