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

using namespace std;

const int N = 1500 + 7;
const long double INF = 1e9;
const int MOD = 104659;

int n, m;
vector <pair <int, long double>> g[N];
priority_queue <pair <long double, int>> pq;
long double ans[N];
int cnt[N];

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

        cin >> n >> m;
        for (int i = 2; i <= n; i++)
                ans[i] = INF;
        for (int i = 1; i <= m; i++)
        {
                int a, b;
                long double c;
                cin >> a >> b >> c;
                c = log2(c);
                g[a].push_back({b, c});
                g[b].push_back({a, c});
        }

        pq.push({0, 1});
        cnt[1] = 1;

        while (!pq.empty())
        {
                long double c = -pq.top().first;
                int a = pq.top().second;
                pq.pop();
                if (c != ans[a])
                        continue;
                for (auto &it : g[a])
                {
                        int b = it.first;
                        long double o = ans[a] + it.second;
                        if (o<ans[b])
                        {
                                ans[b] = o;
                                cnt[b]=0;
                                pq.push({-ans[b], b});
                        }
                        if (o==ans[b])
                        {
                                cnt[b] += cnt[a];
                                if (cnt[b] >= MOD)
                                        cnt[b] -= MOD;
                        }
                }
        }

        for (int i = 2; i <= n; i++)
                cout << cnt[i] << " ";
        cout << "\n";

        return 0;
}