#include<cstdio>
#include<fstream>
#include<vector>
#include<queue>
#include<cmath>

using namespace std;

const int MaxN = 1501;
const double eps = 1e-10;
const int Mod = 104659;
const double InF = 100000000;

const char InFile[] = "dmin.in";
const char OutFile[] = "dmin.out";

int N,M,sol[MaxN];
double d[MaxN];
bool inQ[MaxN];
vector< pair<int,double> > G[MaxN];
queue<int> Q;

double modul( double x )
{
	return x > 0 ? x : -x;
}

void BellMan_Ford()
{
	int nod;
	vector< pair<int,double> >::iterator it,iend;
	for( nod = 1 ; nod <= N ; ++nod )
		{
			d[nod] = InF;
			sol[nod] = 0;
			inQ[nod] = false;
		}
	d[1] = 0;
	sol[1] = 1;
	Q.push(1);
	inQ[1] = true;
	while( !Q.empty() )
		{
			nod = Q.front();
			Q.pop();
			inQ[nod] = false;
			iend = G[nod].end();
			it = G[nod].begin();
			for( ; it != iend ; ++it )
				{
					if( modul(d[it->first] - d[nod] - it-> second) < eps )
						{
							sol[it->first] = ( sol[it->first]+sol[nod] ) % Mod;
							if( !inQ[it->first] )
								{
									Q.push(it->first);
									inQ[it->first] = true;
								}
						}
					if( d[it->first] - d[nod] - it->second > eps )
						{
							d[it->first] = d[nod] + it->second;
							sol[it->first] = sol[nod];
							if( !inQ[it->first] )
								{
									Q.push(it->first);
									inQ[it->first] = true;
								}
						}
				}
		}
}

int main()
{
	ifstream fin( InFile );
	ofstream fout( OutFile );
	fin >> N >> M;
	int i,x,y;
	double z;
	for( i = 0 ; i < M ; ++i )
		{
			fin >> x >> y >> z;
			G[x].push_back(make_pair(y,log(z)));
			G[y].push_back(make_pair(x,log(z)));
		}
	BellMan_Ford();
	for( i = 2 ; i <= N ; ++i )
		fout << sol[i] << ' ';
	fout << '\n';
	fin.close();fout.close();
	return 0;
}