#include <fstream>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;

ifstream cin ("dmin.in");
ofstream cout ("dmin.out");

struct muchie{
    int st;
    long long lung;
};

int n,m;
int nr[50005];
vector<muchie>ad[50005];
double len[50005];
priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> pq;

int main() {
    int a,b,c,vf;
    double l,lnw;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>a>>b>>c;
        ad[a].push_back({b,c});
        ad[b].push_back({a,c});
    }
    for(int i=1;i<=n;i++)
        len[i]=1e18;
    len[1]=0;
    nr[1]=1;
    pq.push({0,1});
    while(!pq.empty()){
        l=pq.top().first;
        vf=pq.top().second;
        pq.pop();
        if(l>len[vf])
            continue;
        for(muchie&i:ad[vf]){
            lnw=len[vf]+log((double)i.lung);
            if(len[i.st]>lnw) {
                len[i.st]=lnw;
                nr[i.st]=nr[vf];
                pq.push({len[i.st],i.st});
            }
            else if(fabs(len[i.st]-lnw)<1e-12)
                nr[i.st]=(nr[i.st]+nr[vf])%104659;
        }
    }
    for(int i=2;i<=n;i++)
        cout<<nr[i]<<" ";
    return 0;
}