#include<cstdio>
#include<cmath>
#include<vector>
#define infile "dmin.in"
#define outfile "dmin.out"
#define nMax 1513
#define eps 0.000001
#define inf (~(1<<31))
#define modulo 104659

using namespace std;

vector < pair <int, double> > v[nMax];
double cMin[nMax];
int ap[nMax];
int ph[nMax];
int h[nMax];
int n, m, hn;

void combTop(int c) {
  int f = c>>1;
  while(f && cMin[h[f]] > cMin[h[c]]) {
    swap(h[f], h[c]);
    swap(ph[h[f]], ph[h[c]]);
    c = f, f >>= 1;
  }
}

void combDown(int f) {
  int c = f<<1;
  while(c <= n) {
    if(c+1 <= n && cMin[h[c+1]] < cMin[h[c]]) ++c;
    if(cMin[h[f]] > cMin[h[c]]) {
      swap(h[f], h[c]);
      swap(ph[h[f]], ph[h[c]]);
      f = c, c <<= 1;
    } else break;
  }
}

void push(int x) {
  h[ph[x]=++hn] = x;
  combTop(hn);
}

int pop() {
  int x = h[1];
  h[1] = h[hn--];
  combDown(1);
  return x;
}

void read() {
  scanf("%d %d\n", &n, &m);
  for(int i = 1; i <= m; ++i) {
    int x, y, z;
    scanf("%d %d %d\n", &x, &y, &z);
    v[x].push_back(make_pair(y, log(z)));
    v[y].push_back(make_pair(x, log(z)));
  }
}

void solve() {

  for(int i = 0; i <= n; ++i)
    cMin[i] = inf;

  cMin[1] = 0, ap[1] = 1, push(1);

  while(hn) {
    int x = pop();
    for(unsigned i = 0; i < v[x].size(); ++i) {
      if(abs(cMin[x] + v[x][i].second - cMin[v[x][i].first]) < eps)
        ap[v[x][i].first] = (ap[v[x][i].first] + ap[x]) % modulo;
      else if(cMin[x] + v[x][i].second < cMin[v[x][i].first]) {
        ap[v[x][i].first] = ap[x];
        cMin[v[x][i].first] = cMin[x] + v[x][i].second;
        if(ph[v[x][i].first]) combTop(ph[v[x][i].first]);
        else push(v[x][i].first);
      }
    }
  }
}

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

int main() {
  freopen(infile, "r", stdin);
  freopen(outfile, "w", stdout);

  read();
  solve();
  write();

  fclose(stdin);
  fclose(stdout);
  return 0;
}