#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
#define maxn 1510
#define inf 99999999
#define mod 104659
#define eps 0.00000001
using namespace std;
FILE *f=fopen("dmin.in", "r");
FILE *g=fopen("dmin.out", "w");

int N, M, sol[maxn];
double D[maxn];
vector< pair < int, double > > G[maxn];
queue<int> Q;
bool viz[maxn];
void BellmanFord() {
    int i, x;
  
    for(i=1; i<=N; i++) {
         viz[i] = false;
		D[i] = inf;
    }
    viz[1] = true;
    Q.push(1);
    D[1] = 0; 
	sol[1] = 1;
    while(!Q.empty()) {
		
		x=Q.front();
		Q.pop();
		viz[x] = false;
		for(vector< pair < int, double > >::iterator it=G[x].begin(); it!=G[x].end(); it++) {
			if(eps < D[(*it).first] -D[x] - (*it).second) {
				D[(*it).first] = D[x] + (*it).second;
				sol[(*it).first] = sol[x];
					if(!viz[(*it).first]) {
                        viz[(*it).first] = 1;
                        Q.push((*it).first);
					}
			}
			else 
				if(D[x] + (*it).second - D[(*it).first] <= eps) {
                   sol[(*it).first] += sol[x];
                   sol[(*it).first] %= mod;
				}
		}
    }
}

int main() {
    
    int i, j, x, y;

    fscanf(f, "%d %d\n", &N, &M);
    for(i=1; i<=M; i++) {
         fscanf(f, "%d %d %d\n", &x, &y, &j);
         double cost = (double)log(j);

         G[x].push_back( make_pair(y, cost) );
         G[y].push_back( make_pair(x, cost) );
    }

    BellmanFord();

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

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