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

using namespace std;

ifstream fin ("dmin.in");
ofstream fout ("dmin.out");

const int Dim = 1e5;
int n,m,P[Dim];
const double eps = 0.0000000001;
using VI = vector < pair  < int,  double > > ;
using VVI = vector < VI >;
priority_queue < pair < double, int >  ,vector < pair < double, int > >, greater<pair < double, int >>> Q;  
double D[Dim];
const int mod = 104659;
VVI G;

int main() {
	
	fin >> n >> m;
	G = VVI ( n + 1 );
	int x,y,w;
	for ( ; m > 0; --m) {
		
		fin >> x >> y >> w;
		G[x].push_back({y,log10(w)});
		G[y].push_back({x,log10(w)});
	}
	Q.push({0,1});
	D[1] = 0;
	for ( int i = 2; i <= n; ++i)
		D[i] = 0x3f3f3f3f;
	P[1] = 1;
	while ( !Q.empty() ) {
		double dx = Q.top().first;
		int x = Q.top().second;
		Q.pop();
		if ( dx  -eps > D[x] )
			continue;
		for ( const auto & y : G[x] ) {
			if ( D[y.first] - eps > D[x] + y.second) { 
				D[y.first] = D[x] + y.second;
				P[y.first] = P[x];
				Q.push({D[y.first],y.first});
			}
			else if ( fabs(D[y.first] - D[x] - y.second) <= eps) {
					P[y.first] += P[x];  
					P[y.first] %= mod;
				}
		}
	}	
	
	for ( int i = 2; i <= n; ++i)
		fout << P[i] << " ";
}