using namespace std;
#include <fstream>
#include <cstdio>
#include <vector>
#include <cmath>
#define INFINIT 1<<30
#define EPS 1E-9

#define NN 1505

int egale(double x, double y){
	return abs(x-y)<=EPS;
}

vector <pair<int, double> > G[NN];
int n,   nr[NN] , v[NN];
double d[NN];

int main(){
	ifstream fin ("dmin.in");
	int m,i,j,c;
	fin>>n>>m;
	for( ; m ; --m){
		fin>>i>>j>>c;
		G[i].push_back(make_pair(j,log(c)));
		G[j].push_back(make_pair(i,log(c)));
	}
	/*
	for(int i=1;i<=n;++i){
			printf("%d : ",i);
			for(unsigned j=0;j<G[i].size(); ++j)
				printf("(%d,%lf) ", G[i][j].first, exp(G[i][j].second));
			printf("\n");
	}
	*/
	for(int i=0;i<=n;++i)
		d[i]=INFINIT,nr[i]=0;;
	v[1]=1;
	nr[1]=1;
	d[1]=0;
	for(unsigned int i=0; i<G[1].size(); ++i)
		nr[G[1][i].first] = nr[1] , d[G[1][i].first] =G[1][i].second;
	for(int kk=1;kk<n;++kk){
		int dmin=0;
		for(int i=1;i<=n;++i)
			if(v[i]==0 && d[dmin]>d[i])
				dmin=i;
		if(!dmin){ 
			printf("break\n");
			break;
		}
		v[dmin]=1;
		for(unsigned int i=0; i<G[dmin].size(); ++i)
			if(v[G[dmin][i].first]==0){
				if( d[G[dmin][i].first] > d[dmin]+G[dmin][i].second+EPS)
					d[G[dmin][i].first] = d[dmin]+G[dmin][i].second, nr[ G[dmin][i].first ] =nr[dmin];
				else
					if(egale(d[ G[dmin][i].first ] , d[ dmin ]+G[ dmin ][i].second) )
						nr[G[dmin][i].first] = (nr[G[dmin][i].first] + nr[dmin]) % 104659;
			}
	}
	freopen("dmin.out","w",stdout);
	for(int i=2 ; i<=n ; ++i)
		printf("%d ", nr[i]);
	printf("\n");
	return 0;
}