#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
#define maxn 1507
#define inf 29999999
#define mod 104659
#define eps 0.0000001
using namespace std;
FILE *f=fopen("dmin.in", "r");
FILE *g=fopen("dmin.out", "w");
int i,t,x,y;
int n, m, nr[maxn];
double D[maxn];
vector< pair < int, double > > L[maxn];
vector< pair < int, double > >::iterator it;
queue<int> Q;
bool viz[maxn];
int main() {
	fscanf(f, "%d %d\n", &n, &m);
    for(i=1; i<=m; i++) {
		
		fscanf(f, "%d %d %d\n", &x, &y, &t);
		
		double c= (double)log(t);
		
		L[x].push_back( make_pair(y, c) );
		L[y].push_back( make_pair(x, c) );
    }
	
	
	for(i=2; i<=n; i++) {
		D[i]=inf;
    }
    viz[1] = 1;
    Q.push(1);
    D[1] = 0; 
	nr[1] = 1;
    while(!Q.empty()) {
		
		x=Q.front();
		Q.pop();
		viz[x] = 0;
		for(it=L[x].begin(); it!=L[x].end(); it++) {
			if(eps < D[(*it).first] -D[x] - (*it).second) {
				D[(*it).first] = D[x] + (*it).second;
				nr[(*it).first] = nr[x];
					if(!viz[(*it).first]) {
                        viz[(*it).first] = 1;
                        Q.push((*it).first);
					}
			}
			else 
				if(D[x] + (*it).second - D[(*it).first] <= eps) {
                   nr[(*it).first] += nr[x];
                   nr[(*it).first] %= mod;
				}
		}
    }

    for(i=2; i<=n; i++) {
		fprintf(g, "%d ", nr[i]);
    }

    fclose(f);
	fclose(g);
    return 0;
}