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

const int MOD = 104659;
const long long INF = 1e18;

struct Edge {
    int to;
    long long cost;
};

vector<vector<Edge>> adj;
vector<long long> dist;
vector<int> ways;

void dijkstra(int start) {
    int n = adj.size();
    dist.assign(n, INF);
    ways.assign(n, 0);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;

    dist[start] = 1;
    ways[start] = 1;
    pq.push({1, start});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (d > dist[u]) continue;

        for (auto &edge : adj[u]) {
            int v = edge.to;
            long long new_dist = d * edge.cost;

            if (new_dist < dist[v]) {
                dist[v] = new_dist;
                ways[v] = ways[u];
                pq.push({new_dist, v});
            } else if (new_dist == dist[v]) {
                ways[v] = (ways[v] + ways[u]) % MOD;
            }
        }
    }
}

int main() {
    ifstream cin("dmin.in");
    ofstream cout("dmin.out");

    int N, M;
    cin >> N >> M;

    adj.resize(N + 1);

    for (int i = 0; i < M; ++i) {
        int x, y;
        long long c;
        cin >> x >> y >> c;
        adj[x].push_back({y, c});
        adj[y].push_back({x, c});
    }

    dijkstra(1);

    for (int i = 2; i <= N; ++i) {
        cout << ways[i] << " ";
    }
    cout << endl;

    return 0;
}