#include <stdio.h>
#include <math.h>
#include <vector>
#define Nmax 1502
#define pb push_back
#define mp make_pair
#define y first
#define c second
#define Mod 104659
#define INF 2147000000
#define eps 0.000001

using namespace std;

vector< pair< int,int > > v[Nmax];
int H[Nmax],poz[Nmax],Nr[Nmax];
double D[Nmax];
int n,m,dh;

inline double Abs(double x){ return x>0 ? x:-x; }
inline int egal(double x,double y){
	return Abs(x-y) < eps;
}
inline int mai_mare(double x,double y){
	return( x-y>eps );
}

inline void swap(int i,int j){
	int aux=H[i]; H[i]=H[j]; H[j]=aux;
	poz[H[i]]=i;
	poz[H[j]]=j;
}
inline void Up(int k){
	while( k/2 && mai_mare(D[H[k/2]], D[H[k]]) ){
		swap(k,k/2);
		k=k/2;
	}
}
inline void Down(int k){
	int min=0;
	while( min != k ){
		min=k;
		if( 2*min<=dh && mai_mare(D[H[k]],D[H[2*min]]) ) k=2*min;
		if( 2*min+1<=dh && mai_mare(D[H[k]],D[H[2*min+1]])) k=2*min+1;
		swap(min,k);
	}
}

void Dijkstra(){
	vector< pair< int,int > >:: iterator it;
	int i,pmin;
	
	for(i=1;i<=n;++i) H[i]=poz[i]=i, D[i]=INF*1.00;
	D[1]=0.00; Nr[1]=1;
	dh=n;
	
	while( dh ){
		pmin=H[1];
		swap(1,dh);
		dh--;
		Down(1);
		
		for(it=v[pmin].begin(); it!=v[pmin].end(); ++it)
			if( mai_mare(D[it->y], D[pmin] + log(it->c)) ){
				D[it->y] = D[pmin] + log(it->c);
				Nr[it->y] = Nr[pmin];
				Up(poz[it->y]);
			}else
			if( egal(D[it->y],D[pmin] + log(it->c)) )
				Nr[it->y]=( Nr[it->y] + Nr[pmin]) % Mod;
	}
}

int main(){
	int i,x,y,z;
	freopen("dmin.in","r",stdin);
	freopen("dmin.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;++i){
		scanf("%d%d%d",&x,&y,&z);
		v[x].pb(mp(y,z));
		v[y].pb(mp(x,z));
	}
	
	Dijkstra();
	
	printf("%d",Nr[2]);
	for(i=3;i<=n;++i) printf(" %d",Nr[i]);
	printf("\n");
	fclose(stdin); fclose(stdout);
	return 0;
}