#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],U[1<<13];
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);
    }
    U[1]=1;
    Q.push(make_pair(0,1));
    for(i=2;i<=n;++i) Cost[i]=1<<20;
    while(!Q.empty())
    {
        int nod=Q.top().second;
        double cost=Q.top().first;
        Q.pop();
        //g<<cost<<'\n';
        if(abs(Cost[nod]-cost)>EPS) continue;
        dp[nod]=(dp[nod]+U[nod])%Xp;
        U[nod]=0;
        for(i=0;i<(int)G[nod].size();++i)
        {
            int M=G[nod][i];
            int node=x[M]+y[M]-nod;
            if(Cost[node]>Cost[nod]+z[M])
            {
                Cost[node]=Cost[nod]+z[M];
                U[node]=dp[nod];
                Q.push(make_pair(Cost[node],node));
            }
            else if(abs(Cost[node]-Cost[nod]-z[M])<=EPS)
            {
                U[node]+=dp[nod];
                //Q.push(make_pair(Cost[node],node));
            }
        }
    }
    for(i=2;i<=n;++i) g<<dp[i]<<' ';
    return 0;
}