#include <stdio.h>
#include <math.h>
#define MAXN 1500
#define MAXM 2500
#define INF_DB 2000000000.0
#define EPS 0.0000001
#define MOD 104659
double cost[2 * MAXM];
int ult[MAXN], nod[2 * MAXM], next[2 * MAXM];
double dmin[MAXN];
int nrd[MAXN];
int heap[MAXN], ph[MAXN];

inline char cmp(double x, double y){
  if(x - y > EPS)
    return 1;
  else  if(y - x > EPS)
    return -1;
  else
    return 0;
}

inline void intersch(int a, int b){
  int aux;
  ph[heap[a]] = b;
  ph[heap[b]] = a;
  aux = heap[a];  heap[a] = heap[b];  heap[b] = aux;
}

inline void cobor(int x, int dr){
  int best;
  char g = 1;
  while(2 * x + 1 < dr && g){
    best = 2 * x + 1;
    if(2 * x + 2 < dr && cmp(dmin[heap[best]], dmin[heap[2 * x + 2]]) == 1)
      best = 2 * x + 2;
    if(cmp(dmin[heap[x]], dmin[heap[best]]) == 1){
      intersch(x, best);
      x = best;
    }
    else
      g = 0;
  }
}

inline void urc(int x){
  while(x > 0 && cmp(dmin[heap[(x - 1) / 2]], dmin[heap[x]]) == 1){
    intersch((x - 1) / 2, x);
    x = (x - 1) / 2;
  }
}

inline void add(int x, int *dr){
  if(ph[x] == -1){
    heap[*dr] = x;
    ph[x] = *dr;
    urc(*dr);
    (*dr)++;
  }
  else
    urc(ph[x]);
}

inline void dijkstra(int n){
  int i, dr = 1, poz, nd;
  for(i = 0; i < n; i++){
    ph[i] = -1;
    dmin[i] = INF_DB;
    nrd[i] = 0;
  }
  dmin[0] = 0.0;
  nrd[0] = 1;
  heap[0] = 0;
  ph[0] = 0;
  while(dr > 0){
    nd = heap[0];
    intersch(0, dr - 1);
    dr--;
    cobor(0, dr);
    poz = ult[nd];
    while(poz > -1){
      if(cmp(dmin[nod[poz]], dmin[nd] + cost[poz]) == 1){
        dmin[nod[poz]] = dmin[nd] + cost[poz];
        nrd[nod[poz]] = nrd[nd];
        add(nod[poz], &dr);
      }
      else  if(cmp(dmin[nod[poz]], dmin[nd] + cost[poz]) == 0){
        nrd[nod[poz]] += nrd[nd];
        if(nrd[nod[poz]] >= MOD)
          nrd[nod[poz]] -= MOD;
      }
      poz = next[poz];
    }
  }
}

int main(){
  FILE *in = fopen("dmin.in", "r");
  int n, m, x, y, z, dr = 0, i;
  fscanf(in, "%d%d", &n, &m);
  for(i = 0; i < n; i++)
    ult[i] = -1;
  for(i = 0; i < m; i++){
    fscanf(in, "%d%d%d", &x, &y, &z);
    x--;  y--;
    cost[dr] = cost[dr + 1] = log(z);
    nod[dr] = y;
    next[dr] = ult[x];
    ult[x] = dr;
    dr++;
    nod[dr] = x;
    next[dr] = ult[y];
    ult[y] = dr;
    dr++;
  }
  fclose(in);
  dijkstra(n);
  FILE *out = fopen("dmin.out", "w");
  for(i = 1; i < n; i++)
    fprintf(out, "%d ", nrd[i]);
  fclose(out);
  return 0;
}