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

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

const int N = 1502;
const double eps = 0.0000001;
const int M = 104659;

int n, m, sol[N], nod;
double dist[N];
bool ver[N];
vector<pair<int, double> > v[N];
queue<int> q;

void dijkstra() {
	int i;
	vector<pair<int, double> >::iterator it;
	
	for(i = 1; i<=n; ++i)
		dist[i] = 29999999.0;
	
	ver[1] = true;
	q.push(1);
	dist[1] = 0;
	sol[1] = 1;
	
	while(!q.empty()) {
		nod = q.front();
		q.pop();
		ver[nod] = false;
		
		for(it = v[nod].begin(); it!=v[nod].end(); ++it) {
			if(dist[it->first] - dist[nod] - it->second > eps) {
				dist[it->first] = dist[nod] + it->second;
				sol[it->first] = sol[nod];
				
				if(!ver[nod]) {
					q.push(it->first);
					ver[it->first] = true;
				}
			}
			else if(dist[nod] + it->second - dist[it->first] <= eps) {
				sol[it->first] += sol[nod];
				if(sol[it->first] > M)
					sol[it->first] -= M;
			}
		}
	}
}

int main() {
	int i, x, y;
	double c;
	
	in >> n >> m;
	
	for(i = 1; i<=m; ++i) {
		in >> x >> y >> c;
		c = log(c);
		
		v[x].push_back(pair<int, double>(y, c));
		v[y].push_back(pair<int, double>(x, c));
	}
	
	dijkstra();
	
	for(i = 2; i<=n; ++i)
		out << sol[i] << " ";
	
	return 0;
}