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

#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;
const long double EPS = 1e-9;

struct Muchii {
	int nod;
	long double cost;

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

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

static inline void dj() {
	for(int i = 1; i <= n; i++)
		dp[i] = INF;
	ans[1] = 1;
	dp[1] = 0;
	pq.push({1, 0});
	int cur;
	while(!pq.empty()) {
		cur = pq.top().nod;
		pq.pop();
		for(const Muchii &M : adj[cur]) {
			if(dp[M.nod] - dp[cur] - M.cost > EPS) {
				ans[M.nod] = 0;
				dp[M.nod] = dp[cur] + M.cost;
				pq.push({M.nod, dp[M.nod]});
			}
			if(abs(dp[M.nod] - dp[cur] - M.cost) < EPS)
				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;
	double c;
	while(m--) {
		cin >> x >> y >> c;
		c = log(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;
}