#include <fstream>
#include <vector>
#include <queue>
#include <cmath>

using namespace std;

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

const int MOD = 104659;
const double INF = 1e18;
const double EPS = 1e-9;

vector <int> dijkstra(vector<vector<pair<int,int>>> &graph, int start,int n) {
    priority_queue<pair<double,int>> pq;
    vector <double> dist(n+1, INF);
    vector <int> dp(n+1,0);
    dp[start]=1;
    dist[start] = 0.0;
    pq.push({0.0, start});
    while (!pq.empty()) {
        auto [x,y] = pq.top();
        pq.pop();
        x=-x;
        if (x != dist[y]) {
            continue;
        }
        for (auto& edge : graph[y]) {
            int next = edge.first;
            int cost = edge.second;
            double log_cost = log(cost);
            if (dist[next] > dist[y] + log_cost + EPS) {
                dist[next] = dist[y] + log_cost;
                dp[next] = dp[y];
                pq.push({-dist[next], next});
            }
            else if (abs(dist[next] - (dist[y] + log_cost)) <= EPS) {
                dp[next] = (dp[next] + dp[y]) % MOD;
            }
        }
    }
    return dp;
}

int main() {
    int n,m;
    fin>>n>>m;

    vector <vector <pair<int,int>>> graph(n+1);

    for (int i=1;i<=m;i++) {
        int a,b,c;
        fin>>a>>b>>c;
        graph[a].push_back({b,c});
        graph[b].push_back({a,c});
    }
    vector <int> rez=dijkstra(graph,1,n);
    for (int i=2;i<=n;i++) {
        fout<<rez[i]<<" ";
    }
    return 0;
}