#include <bits/stdc++.h>
using namespace std;
ifstream f("dmin.in");
ofstream g("dmin.out");
const int Xp=104659;
const double EPS=1e-10;
int n,m,i,j,x[1<<15],y[1<<15],dp[1<<11];
double Cost[1<<11],z[1<<12];
vector <int> G[1510];
priority_queue <pair <double,int> ,vector <pair <double,int> > ,greater <pair <double,int > > > Q;
int main()
{
    f>>n>>m;
    for(i=1;i<=m;++i)
    {
        f>>x[i]>>y[i]>>z[i];
        z[i]=log2(z[i]);
        G[x[i]].push_back(i);
        G[y[i]].push_back(i);
    }
    dp[1]=1;
    Q.push(make_pair(0,1));
    for(i=1;i<=n;++i) Cost[i]=-1;
    while(!Q.empty())
    {
        int nod=Q.top().second;
        double cost=Q.top().first;
        Q.pop();
        if(Cost[nod]!=-1) continue;
        Cost[nod]=cost;
        for(i=0;i<(int)G[nod].size();++i)
        {
            int M=G[nod][i];
            int node=x[M]+y[M]-nod;
            if(Cost[node]!=-1)
                if(abs(Cost[nod]-Cost[node]-z[M])<=EPS) dp[nod]=(dp[nod]+dp[node])%Xp;
            Q.push(make_pair(Cost[nod]+z[M],node));
        }
    }
    for(i=2;i<=n;++i) g<<dp[i]<<' ';
    return 0;
}