#include <bits/stdc++.h>
#define MAXN 1500
#define cost first
#define nod second
#define MOD 104659

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

struct Edge {
   double cost;
   int nod;
   bool operator <(const Edge &x) const {
       return cost > x.cost;
   }
};

std::priority_queue <Edge> pq;

double dist[MAXN + 1];
bool viz[MAXN + 1];
int dp[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 = 1; i <= n; i++)
       dist[i] = 2.0 * 1e9;
    pq.push({0, 1});
    dp[1] = 1;
    while(!pq.empty()) {
       int nod = pq.top().nod;
       double cost = pq.top().cost;
       if(!viz[nod]) {
          dist[nod] = cost;
          viz[nod] = 1;
          for(auto it : g[nod])
            if(equal(dist[it.nod] + it.cost, dist[nod])) {
              dp[nod] += dp[it.nod];
              mod(dp[nod]);
            }
       }
       pq.pop();
       for(auto it : g[nod])
          if(dist[nod] + it.cost < dist[it.nod])
             pq.push({dist[nod] + it.cost, it.nod});
    }
    for(i = 2; i <= n; i++)
       fprintf(fout,"%d " ,dp[i]);
    fclose(fi);
    fclose(fout);
    return 0;
}