#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
#define maxn 1510
#define inf 99999999
#define mod 104659
#define eps 0.00001
#define PB push_back
#define MKP make_pair
#define ff first
#define ss second
#define PII pair<int, double>

int N, M, sol[maxn], viz[maxn];
double dmin[maxn];
vector<PII> G[maxn];

void BellmanFord() {
    int i, p;
    queue<int> Q;
    bool InQueue[maxn];
    for(i=1; i<=N; i++) {
         InQueue[i] = false;
         dmin[i] = inf;
    }
    InQueue[1] = true;
    Q.push(1);
    dmin[1] = 0; sol[1] = 1;
    while(!Q.empty()) {
         p = Q.front(); Q.pop();
         InQueue[p] = false;
         for(vector<PII>::iterator it=G[p].begin(); it!=G[p].end(); it++) {
              if(eps < dmin[(*it).ff] - dmin[p] - (*it).ss) {
                   dmin[(*it).ff] = dmin[p] + (*it).ss;
                   sol[(*it).ff] = sol[p];
                   if(!InQueue[(*it).ff]) {
                        InQueue[(*it).ff] = 1;
                        Q.push((*it).ff);
                   }
              }
              else if(dmin[p] + (*it).ss - dmin[(*it).ff] <= eps) {
                   sol[(*it).ff] += sol[p];
                   sol[(*it).ff] %= mod;
              }
         }
    }
}

int main() {
    FILE *f1=fopen("dmin.in", "r"), *f2=fopen("dmin.out", "w");
    int i, j, p, q;

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

         G[p].PB( MKP(q, cost) );
         G[q].PB( MKP(p, cost) );
    }

    BellmanFord();

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

    fclose(f1); fclose(f2);
    return 0;
}