#include <cstdio>
#include <queue>
#include <cmath>
#include <algorithm>

using namespace std;

const int N = 1505, MOD =104659;

const double INF = 2000000000, eps = 0.000000001;

double dist[N];

int n, pr[N], rez[N];

bool f[N];

vector<pair<int,double> > L[N];

queue<int> Q;

void read() {
  freopen("dmin.in", "r", stdin);
  freopen("dmin.out", "w", stdout);
  int m,x,y,c;

  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; ++ i) {
    scanf("%d%d%d", &x, &y, &c);
    L[x].push_back(make_pair(y, log10((double)c)));
    L[y].push_back(make_pair(x, log10((double)c)));
  }
}

void init() {
  for (int i = 1; i <= n; ++ i)
    dist[i] = INF;
}

bool mic(double x, double y);

void solve() {
  int nod;
  Q.push(1);
  dist[1] = 0;
  f[1] = 1;

  while (! Q.empty()) {
    nod = Q.front();
    Q.pop();
    f[nod] = ! f[nod];
    for (vector<pair<int,double> >::iterator it = L[nod].begin(); it != L[nod].end(); ++ it)
      if (mic(dist[nod] + it -> second, dist[it -> first])) {
        dist[it -> first] = dist[nod] + it -> second;
        if (! f[it -> first]) {
          f[it -> first] = ! f[it -> first];
          Q.push(it -> first);
        }
      }
  }
}

bool comp(const int &a, const int &b) {
  return dist[a] < dist[b];
}

bool mic(double a, double b) {
    return b - a > eps ? 1 : 0;
}

bool egal(double a, double b) {
    return a - b < eps ? 1 : 0;
}

void afis() {
  for (int i = 2; i <= n; ++ i)
    pr[i] = i;
  sort(pr + 2, pr + n + 1, comp);
  rez[1] = 1;
  for (int i = 2; i <= n; ++ i)
    for (vector<pair<int,double> >::iterator it = L[pr[i]].begin(); it != L[pr[i]].end(); ++ it)
      if (egal(dist[it -> first] + it -> second, dist[pr[i]])){
        rez[pr[i]] += rez[it -> first];
        if (rez[pr[i]] > MOD)
          rez[pr[i]] -= MOD;
      }
  for (int i = 2; i <= n; ++ i)
    printf("%d ", rez[i]);
}

int main() {
  read();
  init();
  solve();
  afis();
  return 0;
}