#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1500 + 7;
const double EPS = 1e-14;
const double INF = 1e9;
const int MOD = 104659;
int n, m, o[N];
vector <pair <int, double>> g[N];
double dist[N];

bool cmp(int i, int j)
{
        return dist[i] - dist[j] < 0;
}

int sol[N];

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

        scanf("%d%d", &n, &m);
        for (int i = 0; i < m; i++)
        {
                int a, b, z;
                scanf("%d%d%d", &a, &b, &z);
                double c = log2((double) z);
                g[a].push_back({b, c});
                g[b].push_back({a, c});
        }

        for (int i = 2; i <= n; i++)
                dist[i] = INF;
        queue <int> q;
        q.push(1);

        while (!q.empty())
        {
                int a = q.front();
                q.pop();
                for (auto &it : g[a])
                {
                        int b = it.first;
                        double c = dist[a] + it.second;
                        if (c - dist[b] < EPS)
                        {
                                dist[b] = c;
                                q.push(b);
                        }
                }
        }

        for (int i = 1; i <= n; i++)
                o[i] = i;
        sort(o + 1, o + n + 1, cmp);
        sol[1] = 1;

        for (int k = 1; k <= n; k++)
        {
                int i = o[k];
                for (auto &it : g[i])
                {
                        int j = it.first;
                        double c = dist[i] + it.second;
                        if (fabs(c - dist[j]) < EPS)
                        {
                                sol[j] += sol[i];
                                if (sol[j] >= MOD)
                                        sol[j] -= MOD;
                        }
                }
        }
        for (int i = 1; i <= n; i++)
                printf("%d ", sol[i]);
        printf("\n");


        return 0;
}