#include <algorithm>
#include <stdio.h>
#include <vector>
#include <math.h>

#define MAX 4096
#define restRez 104659
#define eps 0.000001
#define pb push_back
#define mp make_pair
#define f first
#define s second

using namespace std;

int n, m;
vector <pair <int, double> > vctDrum[MAX];
int sel[MAX], poz[MAX], pos[MAX];
double sol[MAX];

inline bool cmp(const int &a, const int &b)
{
	return sol[a] < sol[b];
}

int main()
{
	freopen("dmin.in", "r", stdin);
	freopen("dmin.out", "w", stdout);

	scanf("%d %d", &n, &m);

	for (int i = 1; i <= m; i++)
	{
		int n1, n2, c;
		scanf("%d %d %d", &n1, &n2, &c);

		vctDrum[n1].pb(mp(n2, log((double) c)));
		vctDrum[n2].pb(mp(n1, log((double) c)));
	}

	for (int i = 0; i <= n; i++)
		sol[i] = LONG_MAX;

	sol[1] = 0;

	for (int pasi = 1; pasi < n; pasi++)
	{
		int nod = 0;
		for (int i = 1; i <= n; i++)
			if (!sel[i] && sol[i] < sol[nod])
				nod = i;
		sel[nod] = 1;

		for (int i = 0; i < vctDrum[nod].size(); i++)
			sol[vctDrum[nod][i].f] = min(sol[vctDrum[nod][i].f], sol[nod] + vctDrum[nod][i].s);
	}

	for (int i = 1; i <= n; i++)
		poz[i] = i;

	sort(poz + 1, poz + 1 + n, cmp);

	pos[1] = 1;
	for (int nod = 2; nod <= n; nod++)
		for (int i = 0; i < vctDrum[nod].size(); i++)
			if (fabs(sol[nod] - sol[vctDrum[nod][i].f] - vctDrum[nod][i].s) < eps)
				pos[nod] = (pos[nod] + pos[vctDrum[nod][i].f]) % restRez;

	for (int i = 2; i <= n; i++)
		printf("%d ", pos[i]);

	fclose(stdin);
	fclose(stdout);
	return 0;
}