#include <bits/stdc++.h>
using namespace std;

#define NMAX 1505
#define MOD 104659
#define INF 0x3f3f3f3f
#define EPS 0.000000001

int n, m;
vector<pair<int, double> >graph[NMAX];
double dist[NMAX];
int dp[NMAX];

void read() {
  scanf("%d %d ", &n, &m);

  for (int i = 1; i <= m; i++) {
    int x, y, z;
    scanf("%d %d %d ", &x, &y, &z);
    double logz = log(z);
    graph[x].push_back({y, logz});
    graph[y].push_back({x, logz});
  }
}

void dijkstra() {
  fill(dist, dist + n + 1, INF);

  dist[1] = 1;

  priority_queue<pair<double, int>, vector<pair<double, int> >, greater<pair<double, int> > > q;

  q.push({0, 1});

  while (!q.empty()) {
    int node = q.top().second;
    q.pop();

    for (auto it: graph[node]) {
      if (dist[node] + it.second < dist[it.first]) {
        dist[it.first] = dist[node] + it.second;
        q.push({it.second, it.first});
      }
    }
  }
}

void solve() {
  dp[1] = 1;
  for (int i = 2; i <= n; i++) {
    for (auto it: graph[i]) {
      int j = it.first;
      if(abs(dist[i] - (dist[j] + it.second)) < EPS)
        dp[i] = (dp[i] + dp[j]) % MOD;
    }
  }
}

void print() {
  for (int i = 2; i <= n; i++)
    printf("%d ", dp[i]);
}

int main() {
  freopen("dmin.in", "r", stdin);
  freopen("dmin.out", "w", stdout);

  read();
  dijkstra();
  solve();
  print();

  return 0;
}