//drumuri minime infoarena

#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <tuple>
#include <queue>
#include <limits>
#include <cmath>
#include <fstream>

#define EPS 0.0000000001
#define MOD 104659

using namespace std;


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

vector<tuple<int, double> >graf[1600];
double dr[1600];
int nrdr[1600];

void dijkstra(int x, int n)
{
	priority_queue<tuple<double, int> > pq;
	pq.push({ 0.0, x });
	nrdr[x] = 1;
	for (int i = 2; i <= n; i++)
		dr[i] = 1000000;
	while (!pq.empty())
	{
		int a;
		double dmin;
		tie(dmin, a) = pq.top();
		dmin = -dmin;
		pq.pop();
		for (auto &it : graf[a])
		{
			int b;
			double w;
			tie(b, w) = it;
			if (fabs(dr[a] + w - dr[b]) <= EPS)
			{
				nrdr[b] = (nrdr[a] + nrdr[b]) % MOD;
			}
			else
			{
				if (w + dmin < dr[b])
				{
					dr[b] = dmin + w;
					nrdr[b] = nrdr[a];
					pq.push({ -dr[b], b });
				}
			}
		}


	}


}


int main()
{
	long long n, m;
	fin >> n >> m;
	for (long long i = 0; i < m; i++)
	{
		int a, b;
		double w;
		fin >> a >> b >> w;
		graf[a].push_back({ b, log(w) });
		graf[b].push_back({ a, log(w) });
	}
	dijkstra(1, n);
	for (int i = 2; i <= n; i++)
		fout << nrdr[i] << ' ';
	
	

}