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

#define pid pair <int, double>

using namespace std;

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

const int NMAX = 1500;
const int INF = 1e9;
const int MOD = 104659;
const double EPS = 1e-6;

int n, m;
vector <pid> adj[NMAX + 1];

int dp[NMAX + 1];
double dist[NMAX + 1];
bool viz[NMAX + 1];

priority_queue <pid, vector <pid>, greater <pid>> pq;

bool equals(double x, double y){
	double diff = x - y;

	if(diff < 0)
		diff = -diff;

	return (diff < EPS);
}

bool smaller(double x, double y){
	return (y - x > EPS);
}

void dijkstra(int source){
	for(int i = 1; i <= n; i++)
		dist[i] = INF;

	dp[source] = 1;
	dist[source] = 0;
	pq.push({dist[source], source});

	while(!pq.empty()){
		int nod = pq.top().second;
		pq.pop();

		if(!viz[nod]){
			for(auto vec : adj[nod]){
				if(smaller(vec.second + dist[nod], dist[vec.first])){
					dist[vec.first] = vec.second + dist[nod];
					pq.push({dist[vec.first], vec.first});
					dp[vec.first] = 0;
				}
				
				if(equals(vec.second + dist[nod], dist[vec.first]))
					(dp[vec.first] += dp[nod]) %= MOD;
			}

			viz[nod] = true;
		}
	}
}

int main(){

	fin >> n >> m;

	for(int i = 1; i <= m; i++){
		int a, b;
		double c;
		fin >> a >> b >> c;

		c = log2(c); // logaritmare amuzanta

		adj[a].push_back({b, c});
		adj[b].push_back({a, c});
	}

	dijkstra(1);

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

	return 0;
}