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

#define int long long

using namespace std;

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

const int INF = 1e9 + 999;
const int MOD = 104659;
const int MAX = 1502;

struct Muchii {
	int nod, cost;

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

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

void dj() {

	for(int i = 2; i <= n; i++)
		dp[i] = INF;

	ans[1] = 1;
	pq.push({1, 0});
	int cur, 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) {
				ans[M.nod] = ans[cur];

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

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

	cin >> n >> m;

	int x, y, c;
	while(m--) {
		cin >> x >> y >> c;
		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;
}