#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
using namespace std;
vector<pair<pair <int, int> ,int > > hip;
vector<pair<pair <int, int> ,int > > leg[15001];
int lungimeminima[15001];
int cate[15001];
bool compara(pair<pair<int, int> ,int>&a, pair<pair<int, int>,int> &b)
{
	if (a.first.second > b.first.second)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}
int main()
{
	ifstream in("dmin.in");
	ofstream out("dmin.out");
	int n, m, i, x, y, z;
	in >> n;
	in >> m;
	for (i = 1;i <= n;i++)
	{
		lungimeminima[i] = 2000000000;
	}
	cate[1] = 1;
	lungimeminima[1] = 0;
	for (i = 1;i <= m;i++)
	{
		in >> x;
		in >> y;
		in >> z;
		leg[x].push_back(make_pair(make_pair(y, z),x));
		leg[y].push_back(make_pair(make_pair(x, z),y));
	}
	for (i = 0;i < leg[1].size();i++)
	{
		hip.push_back(leg[1][i]);
	}
	make_heap(hip.begin(),hip.end(),compara);
	while (!hip.empty())
	{
		cate[x] %= 104659;
		x = hip[0].second;
		y = hip[0].first.first;
		z = hip[0].first.second;
		pop_heap(hip.begin(), hip.end(), compara);
		hip.pop_back();
		if (z == lungimeminima[y])
		{
			cate[y]+=cate[x];
		}
		else if (z < lungimeminima[y])
		{
			cate[y] = cate[x];
			lungimeminima[y] = z;
			for (i = 0;i < leg[y].size();i++)
			{
				hip.push_back(make_pair(make_pair(leg[y][i].first.first, leg[y][i].first.second*z),y));
				push_heap(hip.begin(), hip.end(), compara);
			}
		}
	}
	for (i = 2;i <= n;i++)
	{
		out << cate[i]% 104659 << " ";
	}

}