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

const int MOD = 104659;
const int NMAX = 10005;
const double INF = 1e18;

int n, m;
vector<pair<int, double>> adj[NMAX]; // Adjacency list with pairs (node, log(cost))
double dist[NMAX]; // Distance array for shortest paths
int ways[NMAX];    // Ways array to count distinct paths modulo MOD

void dijkstra(int source) {
   priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> pq;
    fill(dist, dist + n + 1, INF); // Initialize all distances to infinity
    fill(ways, ways + n + 1, 0);  // Initialize ways to 0

    dist[source] = 0.0; // Distance to the source is 0
    ways[source] = 1;   // There's 1 way to reach the source
    pq.push({0.0, source}); // Push the source into the priority queue

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

        if (current_dist > dist[u]) continue;

        for (auto [v, weight_log] : adj[u]) {
            double new_dist = dist[u] + weight_log;

            if (new_dist < dist[v]) { // Found a better distance
                dist[v] = new_dist;
                ways[v] = ways[u]; // Inherit the number of ways
                pq.push({new_dist, v});
            } else if (abs(new_dist - dist[v]) < 1e-9) { // Same distance
                ways[v] = (ways[v] + ways[u]) % MOD;
            }
        }
    }
}

int main() {
    ifstream fin("dmin.in");
    ofstream fout("dmin.out");

    fin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v, c;
        fin >> u >> v >> c;
        double log_cost = log(c); // Transform cost to logarithmic space
        adj[u].emplace_back(v, log_cost);
        adj[v].emplace_back(u, log_cost); // Add edges (bidirectional)
    }

    dijkstra(1); // Start Dijkstra's algorithm from node 1

    for (int i = 2; i <= n; i++) {
        fout << ways[i] << " ";
    }

    fin.close();
    fout.close();
    return 0;
}