#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#define MAXN 1550
#define MOD 104659
#define INF 5e100

using namespace std;

int n, m;
int cate[MAXN], used[MAXN];
double best[MAXN];
const double EPS = 1e-9;
struct leg
{
	int y;
	double c;
	leg(int y = 0, double c = 0) : y(y), c(c) { }
	bool operator ()(int a, int b)
	{
		return best[a] > best[b];
	}
};
//bool eq(double a, double b)
//{
//    return (a-b) >= -EPS && (a-b) <= EPS;
//}
vector<leg> graf[MAXN];
void citire()
{
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; i++) {
		int x, y, rc;
		scanf("%d %d %d", &x, &y, &rc);
		double c = log(1.0*rc);
		graf[x].push_back(leg(y, c));
		graf[y].push_back(leg(x, c));
	}
}
priority_queue<int, vector<int>, leg> heap;
void solve()
{
	for (int i = 1; i <= n; i++) best[i] = INF;
	best[1] = 0, cate[1] = 1;
    heap.push(1);
    while (!heap.empty()) {
		int top = heap.top();
		heap.pop();
		if (used[top])
			continue;
		used[top] = 1;
        for (auto v : graf[top]) {
            if (best[top] + v.c < best[v.y]) {
				best[v.y] = best[top] + v.c;
				cate[v.y] = cate[top];
                heap.push(v.y);
            }
            else if (fabs(best[v.y]-best[top]-v.c) < EPS)
				cate[v.y] = (cate[v.y] + cate[top]) % MOD;
        }
    }
}

void afisare()
{
    for (int i = 2; i <= n; i++)
		printf("%d ", cate[i]);
	printf("\n");
}

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

	citire();
	solve();
	afisare();

    return 0;
}