#include <stdio.h>
#include <math.h>
#include <vector>
using namespace std;
typedef pair<int, double> graf;
#define NMAX 1510
#define INF 2000000000
#define FOR(i, v) for(vector<graf>::iterator i = v.begin(); i != v.end(); ++i)
#define MOD 104659
#define eps 1e-8
vector <graf> G[NMAX];
int NR[NMAX], H[NMAX];
bool in[NMAX];
double D[NMAX];
int n, m, nr;
double abs(double a){
	if(a > 0) return a;
	return -a;
}
int egal(double a, double b){
	if(abs(a-b) <= eps)
		return 1;
	return 0;
}
void down_heap(int k){
	int son = 1;
	while(son){
		son = 0;
		if(2*k <= nr) son = 2*k;
		if(2*k+1 <= nr && D[H[2*k+1]] < D[H[2*k]]) son ++;
		if(son && D[H[son]] < D[H[k]]){
			swap(H[son], H[k]);
			k = son;
		}
		else son = 0;
	}
}
void up_heap(int k){
	while(k > 1 && D[H[k]] < D[H[k/2]]){
		swap(H[k], H[k/2]);
		k /= 2;
	}
}
void push_heap(int x){
	H[++nr] = x;
	in[x] = true;
	up_heap(nr);
}
int pop_heap(){
	int x = H[1];
	swap(H[1], H[nr]);
	nr--;
	down_heap(1);
	in[x] = false;
	return x;
}
int mic(double a, double b){
	if(b-a > eps)
		return 1;
	return 0;
}
void dij(){
	push_heap(1);
	NR[1] = 1;
	int x, nod;
	double dist;
	while(nr){
		x = pop_heap();
		FOR(i, G[x]){
			nod = i -> first;
			dist = i -> second;
			if(mic(D[x] + dist , D[nod])){
				D[nod] = D[x] + dist;
				NR[nod] = NR[x];
				if(!in[nod]) push_heap(nod);
			}
			else if(egal(D[x] + dist , D[nod])){
				NR[nod] = (NR[nod] + NR[x])%MOD;
				if(!in[nod]) push_heap(nod);
			}
		}
		//SOL[x] = NR[x];
		//NR[x] = 0;
	}
	for(int i = 2; i < n; ++i)
		printf("%d ", NR[i]);
	printf("%d\n", NR[n]);
}
int main(){
	freopen("dmin.in", "r", stdin);
	freopen("dmin.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; ++i){
		int x, y, z;
		double r;
		scanf("%d%d%d", &x, &y, &z);
		r = log10(z);
		G[x].push_back(graf(y,r));
		G[y].push_back(graf(x,r));
	}
	for(int i = 2; i <= n; ++i)
		D[i] = INF;
	dij();
	return 0;
}