#include <bits/stdc++.h>
using namespace std;

const int MAX = 1505, MOD = 104659;
vector<pair<int, double>> graph[MAX];
vector<int> ans;
vector<double> dist;
bitset<MAX> visited;

void dijkstra(int start) {
    priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> q;
    q.push({0.0, start});
    dist[start] = 0.0;
    ans[start] = 1;

    while (!q.empty()) {
        pair<double, int> node = q.top();
        q.pop();
        int u = node.second;
        if (!visited[u]) {
            visited[u] = 1;
            for (pair<int, double> next : graph[u]) {
                int v = next.first;
                double cost = next.second;
                if (dist[v] > dist[u] + cost) {
                    dist[v] = dist[u] + cost;
                    ans[v] = ans[u];
                    q.push({dist[v], v});
                } else if (dist[v] == dist[u] + cost) {
                    ans[v] = (ans[v] + ans[u]) % MOD;
                }
            }
        }
    }
}

int main() {
    ifstream cin("dmin.in");
    ofstream cout("dmin.out");
    int n, m;
    cin >> n >> m;
    ans.assign(n + 1, 0);
    dist.assign(n + 1, DBL_MAX);

    for (int i = 0; i < m; ++i) {
        int x, y, cost;
        cin >> x >> y >> cost;
        double log_cost = log((double)cost);
        graph[x].push_back({y, log_cost});
        graph[y].push_back({x, log_cost});
    }

    dijkstra(1);

    for (int i = 2; i <= n; ++i) {
        cout << ans[i] % MOD << " ";
    }
    cout << endl;

    return 0;
}