#include <fstream>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;

#define Nmax 1511
#define Mmax 100011
#define EPS 0.0000001

#define val first
#define key second

#define oo 1<<30

vector< pair<double,int> > A[Nmax];
queue< int > Q;

double Cost[Nmax];
int Cont[Nmax];

int N,M;
bool Used[Nmax];

ifstream F("dmin.in");
ofstream G("dmin.out");

int main()
{
	F>>N>>M;
	for (int i=1;i<=M;++i)
	{
		int a,b;
		double c;
		F>>a>>b>>c;
		c=log(c);
		A[a].push_back( make_pair( c , b ) );
		A[b].push_back( make_pair( c , a ) );
	}
	for (int i=1;i<=N;++i)
		Cost[i]=29999999.0,
		Cont[i]=0;
	
	int Start=1;
	Cost[Start]=0;
	Cont[Start]=1;
	Q.push( Start );
	Used[Start]=1;
	
	vector< pair<double,int> >::iterator it;
	
	while ( Q.size() )
	{
		int Nbr=Q.front();
		
		Q.pop();
		Used[Nbr]=0;
		
		for ( it=A[Nbr].begin(); it!=A[Nbr].end() ;++it)
		{
			if ( Cost[it->key] - EPS > Cost[Nbr] + it->val )
			{
				Cost[it->key] = Cost[Nbr] + it->val ;
				
				if ( !Used[ it->key ] )
				{
					Q.push( it->key );
					Used[ it->key ]=1;
				}
			}
			
			if ( Cost[Nbr] + it->val - Cost[it->key] <= EPS )
				Cont[it->key] += Cont[Nbr] , Cont[it->key]%=104659;
		}
	}
	
	for (int i=2;i<=N;++i)
		G<<Cont[i]<<' ';
	G<<'\n';
}