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

ifstream fi ("dmin.in");
ofstream fo ("dmin.out");
float dst[DM];
int n, m, a, b, c, val[DM];
struct str
{
	int n;
	float c;
	bool operator < (const str &other) const
	{
		return other.c < c;
	}
} 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();
		for (auto i:v[x.n])
		{
			if (i.c + x.c < dst[i.n])
			{
				dst[i.n] = i.c + x.c;
				val[i.n] = 1;
				pq.push({i.n, dst[i.n]});
			}
			else if (i.c + x.c == dst[i.n])
			{
				++val[i.n];
				val[i.n] %= MD;
				pq.push({i.n, dst[i.n]});
			}
		}
	}
}

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();
	for (int i = 2; i <= n; ++i)
		fo << val[i]%MD << ' ';
	return 0;
}