#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>

int n, m, *leg[1510];
float *cost[1510];
float eps= 1e-10;

void djikstra()
{
  int uz[1510], nr=0, min, numar[1510];
  float d[1510];
//  memset(d, 0x3f3f3f3f, sizeof(d));
  memset(uz, 0, sizeof(uz));
  numar[1]=1;
  for(int i=0; i<=n; ++i) d[i]= 20000000;
  d[1]=0;

  while(nr-n) {
    min=0;
    // aproximare eps
    for(int i=1; i<=n; ++i) if( !uz[i] && d[min] - d[i] > eps) min=i;
    uz[min]= 1;
    nr++;
     for(int i=1; i<=leg[min][0]; ++i)
      if( d[ leg[min][i]] - d[min] - cost[min][i] >eps  && min!=leg[min][i] && !uz[leg[min][i]]) {
        d[ leg[min][i]]= d[min] + cost[min][i];
        numar[ leg[min][i]]= numar[min];
      }
      else if( abs( d[ leg[min][i]] - d[min] - cost[min][i]) <eps && min!=leg[min][i]) {
        numar[ leg[min][i]]+= numar[min];
      }
//    for(int i=1; i<=n; ++i) printf("%.2f ",d[i]);
//    printf("\n");
    numar[min]%= 104659;
  }

  freopen("dmin.out","w",stdout);
  for(int i=2; i<=n; ++i) printf("%d ",numar[i]);
  printf("\n");

  
}

int main()
{
  int x, y, z;
  freopen("dmin.in","r",stdin);
  scanf("%d %d",&n,&m);

  for(int i=1; i<=n; ++i) {
    leg[i]=(int*)malloc(sizeof(int)*2);
    leg[i][0]=0;
    cost[i]=(float*)malloc(sizeof(float)*2);
  }

  for(int i=1; i<=m; ++i) {
    scanf("%d %d %d",&x,&y,&z);

    leg[x][0]++;
    leg[y][0]++;
    leg[x]=(int*)realloc(leg[x], sizeof(int)*(leg[x][0]+5));
    cost[x]=(float*)realloc(cost[x], sizeof(float)*(leg[x][0]+5));
    leg[y]=(int*)realloc(leg[y], sizeof(int)*(leg[y][0]+5));
    cost[y]=(float*)realloc(cost[y], sizeof(float)*(leg[y][0]+5));

    leg[x][ leg[x][0]]= y;
    leg[y][ leg[y][0]]= x;
    cost[x][ leg[x][0]]= log(z);
    cost[y][ leg[y][0]]= log(z);
  }
  djikstra();
  
  return 0;
}