#include<bits/stdc++.h>
using namespace std;
ifstream F("dmin.in");
ofstream G("dmin.out");
double D[1505],d;
int N,M,r[1505],i,a,b,c,o,j,k;
bitset<1505> B;
vector<pair<int,double>> v[1505];
struct C {
    bool operator()(int a,int b)
    {
        return D[a]>D[b];
    }
};
priority_queue<int,vector<int>,C> Q;
int main()
{
    for(F>>N>>M,i=2;i<=N;++i)
        D[i]=1<<30;
    for(i=1;i<=M;++i)
        F>>a>>b>>c,d=log(c),v[a].push_back({b,d}),v[b].push_back({a,d});
    for(Q.push(1),r[1]=1;!Q.empty();) {
        i=Q.top(),Q.pop();
        if(B[i])
            continue;
        for(B[i]=1,j=0,k=v[i].size();j<k;++j){
            o=v[i][j].first,d=v[i][j].second;
            if(fabs(D[o]-D[i]-d)<1e-9)
                r[o]=(r[o]+r[i])%104659;
            else if(D[o]>D[i]+d)
                r[o]=r[i],D[o]=D[i]+d,Q.push(o);
        }
    }
    for(i=2;i<=N;++i)
        G<<r[i]<<' ';
    return 0;
}