#include<stdio.h>
#include<vector>
#include<math.h>

using namespace std;

#define MOD 104659
#define maxN 1505
#define INF (1<<29)
#define eps 1e-10

FILE*f=fopen("dmin.in","r");
FILE*g=fopen("dmin.out","w");

int n,m,i,j,x,y,cst,H[maxN],Poz[maxN],Nr[maxN],nod,nodvcn,L; 
vector< pair<int,double> >G[maxN]; double lg,D[maxN],cstvcn;

inline void citire () {
	
	fscanf(f,"%d %d",&n,&m);
	
	for ( i = 1 ; i <= m ; ++i ){
		fscanf(f,"%d %d %d",&x,&y,&cst);
		lg = log10(cst);
		G[x].push_back(make_pair(y,lg));
		G[y].push_back(make_pair(x,lg));
	}
}

inline void swap ( int &a, int &b ){
	int aux = a;
	a = b;
	b = aux;
}

inline double aabs ( double j ){
	if ( j < 0 )
		return -j;
	return j;
}


inline void urca ( int poz ){
	
	while ( poz > 1 && D[H[poz>>1]] > D[H[poz]] ){
		swap(H[poz>>1],H[poz]);
		swap(Poz[H[poz>>1]],Poz[H[poz]]);
		poz = poz >> 1;
	}
}

inline void coboara ( int x ){
	int y = INF;
	
	while ( x != y ){
		y = x;
		if ( (x<<1) <= L && D[H[x<<1]] < D[H[x]] )	x = x << 1;
		if ( (x<<1) + 1 <= L && D[H[(x<<1)+1]] < D[H[x]] ) x = (x<<1) + 1;
	}
}


inline void insert_heap( int nod ){
	H[++L] = nod;
	Poz[nod] = L;
	urca(L);
}

inline int delete_first( ){
	int nod = H[1];
	swap(H[1],H[L--]);
	coboara(1);
	Poz[nod] = 0;
	return nod;
}


inline void dijkstra () {
	
	for ( Nr[1] = 1, i = 2 ; i <= n ; ++i ){
		D[i] = INF;
	}
	
	insert_heap(1);
	
	while ( L ){
		nod = delete_first();
		
		for ( i = 0 ; i < G[nod].size() ; ++i ){
			nodvcn = G[nod][i].first; cstvcn = G[nod][i].second;
			if ( D[nodvcn] - D[nod] - cstvcn > eps ){
				D[nodvcn] = D[nod] + cstvcn;
				Nr[nodvcn] = Nr[nod];
				
				if ( Poz[nodvcn] ){
					urca(Poz[nodvcn]);
				}
				else{
					insert_heap(nodvcn);
				}
				
			}
			else{
				if (  aabs(D[nod] + cstvcn - D[nodvcn]) <= eps ){
					Nr[nodvcn] += Nr[nod];
					if ( Nr[nodvcn] >= MOD )
						Nr[nodvcn] -= MOD;
				}
			}
		}
		
	}
	
	for ( i = 2 ; i <= n ; ++i ){
		fprintf(g,"%d ",Nr[i]);
	}
}


int main () {
	
	citire();
	
	dijkstra();
	
	fclose(f);
	fclose(g);
	
	return 0;
}