#include <stdio.h>
#include <math.h>
#include <string.h>
#define MOD 104659

#define NMAX 1600
#define FIN "dmin.in"
#define FOUT "dmin.out"
#define infinit 1000000000

typedef struct nod
{
	int info;
	double c;
	struct nod * next; 
}NOD;

NOD * A[NMAX];
FILE * fin, * fout;
int X, Y, N, M, i;
int SEL[NMAX], NR[NMAX];
double D[NMAX];
double C;

void ADD( int info, double c, NOD * &p )
{
	NOD * q;
	q = new NOD; 
	q->info = info; 
	q->c = c; 
	q->next = p; 
	p = q;
}
int equal( double a, double b )
{
	if ( fabs( a - b ) <= 0.0000000001 ) return 1; 
	   else
	    	return 0;
}

void DIJKSTRA( int xp )
{
 int i, found, k = 0;
 double min;
 NOD * p;
 memset( SEL, 0, sizeof(SEL) );
 memset( NR, 0, sizeof(NR) );
 for( i = 1; i <= N; i++ ) D[i] = infinit;
 D[xp] = 0; NR[xp] = 1;
 do
 {
	 min = infinit; found = 0;
	 for( i = 1; i <= N; i++ )
		 if (!SEL[i])
		  if (D[i] < min ) 
			 {
				 min = D[i];
				 k = i;
				 found = 1;
			 }
	  if (found)
	  {
		  p = A[k];
		  while (p!=NULL) 
		  {
			  if (!SEL[p->info])
				  if ( D[k] + p->c < D[p->info] )
				  {
					  D[p->info] = D[k] + p->c;
					  NR[p->info] = NR[k];
				  }else
					  if (equal( D[k] + p->c, D[p->info])) NR[p->info] = (NR[p->info] + NR[k])% MOD;
				  p = p->next;
		  }
          SEL[k] = 1;
	  }
 }while (found);
}

int main()
{
	fin = fopen( FIN, "r" );
	fout = fopen( FOUT, "w" );
	fscanf( fin, "%d %d\n", &N, &M );
	for( i = 1; i <= N; i++ ) A[i] = NULL;
	for( i = 0; i < M; i++ )
	{
		fscanf( fin, "%d %d %f\n", &X, &Y, &C);
		ADD( X, log(C), A[Y] );
		ADD( Y, log(C), A[X] );
	}

    DIJKSTRA(1);
	for( i = 2; i <= N; i++) fprintf(fout, "%d ", NR[i] );
	fprintf( fout, "\n" );
	fclose( fin );
	fclose( fout );
	return 0;
}