#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

const double INF = 2000000000, eps = 0.00000001;

const int N = 2000, MOD = 104659;

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

int n, m, nr, sol[N];

bool f[N];

double dist[N];

pair<int, double> H[N];

void read() {
  int m, x, y, c;
  double nc;
  
  freopen("dmin.in", "r", stdin);
  freopen("dmin.out", "w", stdout);
  
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= m; ++ i) {
    scanf("%d%d%d", &x, &y, &c);
    nc = log10(c);
    L[x].push_back(make_pair(y, nc));
    L[y].push_back(make_pair(x, nc));
  }
}

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

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

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

void coboara_heap(int poz) {
  int p = poz;
  if (2 * poz <= nr && H[p].second > H[2 * poz].second)
    p = 2 * p;
  if (2 * p + 1 <= nr && H[p].second > H[2 * poz + 1].second)
    p = 2 * p + 1;
  if (p != poz) {
    swap(H[p], H[poz]);
    coboara_heap(p);
  }
}

void pop_heap() {
  H[1] = H[nr];
  -- nr;
  coboara_heap(1);
}

void urca_heap(int poz) {
  if (poz == 1)
    return;
  if (H[poz].second < H[poz / 2].second) {
    swap(H[poz], H[poz / 2]);
    urca_heap(poz / 2);
  }
}

void push_heap(pair<int, double> a) {
  ++ nr;
  H[nr] = a;
  urca_heap(nr);
}

void solve() {
  pair<int,double> top;
  int nod = 0, nodc = 0;
  double dis = 0, disc = 0;
  push_heap(make_pair(1, 0));
  sol[1] = 1;
  
  while (nr) {
    top = H[1];
    pop_heap();
    nod = top.first;
    f[nod] = true;
    dis = top.second;
    
    for (vector<pair<int,double> >::iterator it = L[nod].begin(); it != L[nod].end(); ++ it) {
      nodc = it -> first;
      disc = it -> second;
      
      if (less(dist[nod] + disc, dist[nodc])) {
        dist[nodc] = dist[nod] + disc;
        sol[nodc] = sol[nod];
        if (! f[nodc])
          push_heap(make_pair(nodc,dist[nodc]));
      } else if (egal(dist[nod] + disc, dist[nodc])) {
        sol[nodc] += sol[nod];
        if (sol[nodc] > MOD)
          sol[nodc] -= MOD;
      }
    }
  }
}

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

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