#define DM 1501
#define MD 104659
#define inf 0x3f3f3f3f
#define eps 0.0000001
#include <cmath>
#include <cstring>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;

ifstream fi ("dmin.in");
ofstream fo ("dmin.out");
double dst[DM];
int n, m, a, b, c, val[DM];
struct str
{
	int n;
	double c;
	bool operator < (const str &other) const
	{
		return c - other.c > eps;
	}
} x;
priority_queue <str> pq;
vector <str> v[DM];

void dijkstra()
{
	pq.push({1, 0});
	dst[1] = 0;
	while (!pq.empty())
	{
		x = pq.top();
		pq.pop();
		if (dst[x.n] < x.c - eps)
			continue;
		for (auto i:v[x.n])
		{
			if ( - i.c - x.c + dst[i.n] > eps)
			{
				dst[i.n] = i.c + x.c;
				pq.push({i.n, dst[i.n]});
			}
		}
	}
}

void recalibrate()
{
	val[1] = 1;
	for (int i = 2; i <= n; ++i)
 		for (auto j:v[i])
 			if (abs(dst[i] - dst[j.n] - j.c) <= eps)
 				val[i] = (val[j.n] + val[i])%MD;
}

int main()
{
	fi >> n >> m;
	for (int i = 1; i <= n; ++i)
		dst[i] = inf;
	for (int i = 1; i <= m; ++i)
	{
		fi >> a >> b >> c;
		v[a].push_back({b, log10(c)});
		v[b].push_back({a, log10(c)});
	}
	dijkstra();
	recalibrate();
	for (int i = 2; i <= n; ++i)
		fo << val[i]%MD << ' ';
	return 0;
}