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

#define MOD 104659
#define EPS 1e-9  //marja de eroare 0.000000001

using namespace std;

ifstream f("dmin.in");
ofstream g("dmin.out");

const double INF = 1e18;

int n,m,x,y,c;
vector<long long> metode;

void dijkstra(int startNode, const vector<vector<pair<int,int>>>& adj, vector<double>& dist){
    priority_queue<pair<double,int>, vector<pair<double, int>>, greater<pair<double,int>>> pq;

    pq.push({0,startNode});
    dist[startNode] = 0;

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

        if(wt > dist[node])
            continue;

        for(auto& [neigh, cost]: adj[node]){
            double newDist = log(cost) + dist[node];
            if(dist[neigh] > newDist + EPS){
                dist[neigh] = newDist;
                metode[neigh] = metode[node];
                pq.push({newDist, neigh});
            }
            else if(fabs(dist[neigh]-newDist) < EPS){
                metode[neigh] = (metode[neigh] + metode[node]) % MOD;
            }
        }
    }

}

int main(){
    
    f >> n >> m;
    vector<vector<pair<int,int>>> adj(n+1);
    vector<double> dist(n+1, INF);
    metode.resize(n+1, 0);

    for(int i=1; i<=m; i++){
        f >> x >> y >> c;
        adj[x].push_back(make_pair(y,c));
        adj[y].push_back(make_pair(x,c));
    }

    metode[1] = 1;
    dijkstra(1,adj,dist);

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


    return 0;
}