#include <bits/stdc++.h>

//std::ifstream fin ("input.txt");
//std::ofstream fout ("output.txt");

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

long long mod = 104659;

struct Edge{
    int src;
    int dest;
    long long cost;
};

std::vector < std::pair < int, long double > > edge[1505];
long long dp[1505];
long double dist[1505];

void Dijkstra (){
    std::priority_queue < std::pair < long double, int >, std::vector < std::pair < long double, int > >, std::greater < std::pair < long double, int > > > pq;
    pq.push ({0, 1});
    while (!pq.empty()){
        int node = pq.top().second;
        long double cost = pq.top().first;
        for (int i=0; i<edge[node].size(); i++){
            int next = edge[node][i].first;
            long double cost_next = edge[node][i].second;

            if (dist[next] - dist[node] - log10(cost_next) > 0.0){
                dp[next] = dp[node];
                dist[next] = dist[node] + log10(cost_next);
                pq.push ({dist[next], next});
            }
            else if (abs(dist[next] - dist[node] - log10(cost_next)) < 0.000000000000000001)
                dp[next] += dp[node],
                dp[next] %= mod;
        }
        pq.pop();
    }
}

int main()
{
    int V, E,src, dest, i, j, k;
    long double cost;
    fin >> V >> E;

    for (i=0; i<E; i++){
        fin >> src >> dest >> cost;
        edge[src].push_back ({dest, cost});
        edge[dest].push_back ({src, cost});
    }

    for (i=1; i<=V; i++)
        dist[i] = 1e18;

    dp[1] = 1;
    dist[1] = 0;
    Dijkstra ();


    /*
    for (k=1; k<E; k++){
        for (i=0; i<edge.size(); i++){
            src = edge[i].src;
            dest = edge[i].dest;
            cost = edge[i].cost;

            if (dist[dest] > dist[src] * cost){
                dist[dest] = dist[src] * cost;
                dp[dest] = dp[src];
            }
            else if (dist[dest] == dist[src] * cost)
                dp[dest] += dp[src];
        }
    }
    */

    for (i=2; i<=V; i++)
        fout << dp[i] << ' ';

    return 0;
}