#include <bits/stdc++.h>
#define MAXN 1500
#define cost first
#define nod second
#define MOD 104659
#define MAXQ (1 << 19)

std::vector < std::pair <double, int> > g[MAXN + 1];

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

int q[MAXQ];
bool in[MAXN + 1];

const double eps = 1e-8;

inline bool equal(double a, double b) {
    return std::abs(a - b) <= eps;
}

inline void mod(int &x) {
    if(x >= MOD)
      x -= MOD;
}

int main() {
    FILE *fi, *fout;
    int i, n, m, x, y, c;
    fi = fopen("dmin.in" ,"r");
    fout = fopen("dmin.out" ,"w");
    fscanf(fi,"%d %d " ,&n,&m);
    for(i = 1; i <= m; i++) {
       fscanf(fi,"%d %d %d " ,&x,&y,&c);
       double cost = log(c);
       g[x].push_back({cost, y});
       g[y].push_back({cost, x});
    }
    for(i = 2; i <= n; i++)
       dist[i] = 2.0 * 1e9;
    dp[1] = 1;
    int b = 0, e = 1;
    q[0] = 1;
    in[1] = 1;
    while(b != e) {
        for(auto it : g[q[b]])
          if(equal(dist[it.nod], dist[q[b]] + it.cost)) {
              dp[it.nod] += dp[q[b]];
              mod(dp[it.nod]);
              if(!in[it.nod]) {
                 in[it.nod] = 1;
                 q[e++] = it.nod;
                 e &= (MAXQ - 1);
              }
          }else if(dist[it.nod] > dist[q[b]] + it.cost) {
              dist[it.nod] = dist[q[b]] + it.cost;
              dp[it.nod] = dp[q[b]];
              if(!in[it.nod]) {
                 in[it.nod] = 1;
                 q[e++] = it.nod;
                 e &= (MAXQ - 1);
              }
          }
          in[q[b]] = 0;
          b++;
          b &= (MAXQ - 1);
    }
    for(i = 2; i <= n; i++)
       fprintf(fout,"%d " ,dp[i]);
    fclose(fi);
    fclose(fout);
    return 0;
}