#include <bits/stdc++.h>
using namespace std;
ifstream fin("dmin.in");
ofstream fout("dmin.out");
const double INF=1e18,eps=1e-6;
const int mod=104659;
int n, m;
vector<vector<pair<int, double>>> graf;
vector<double> dist;
vector<int> ans;
vector<bool> viz;
void djikstra(int nod){
    priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> q;
    q.push({0,nod});
    dist[nod]=0;
    ans[nod]=1;
    while(!q.empty()){
        nod=q.top().second;
        q.pop();
        if(viz[nod]==0){
            viz[nod]=1;
            for(auto it:graf[nod])
                if(dist[it.first]-dist[nod]-it.second>eps){
                    dist[it.first]=dist[nod]+it.second;
                    q.push({dist[it.first],it.first});
                    ans[it.first]=ans[nod];
                }else if(fabs(dist[it.first]-dist[nod]-it.second)<eps){
                    q.push({dist[it.first],it.first});
                    ans[it.first]=(ans[it.first]+ans[nod])%mod;
                }
        }

    }
}
int main(){
    fin>>n>>m;
    graf.assign(n+1,vector<pair<int, double>>());
    dist.assign(n+1,INF);
    ans.resize(n+1);
    viz.resize(n+1);
    for(int i=1;i<=m;i++){
        int x,y,z;
        double cost;
        fin>>x>>y>>z;
        cost=log2(z);
        graf[x].push_back({y,cost});
        graf[y].push_back({x,cost});
    }
    djikstra(1);
    for(int i=2;i<=n;i++){
        fout<<ans[i]<<" ";
    }

}