#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pf push_front
#define ll long long
#define ull unsigned long long
#define x first
#define y second
#define pi pair<int,int>
#define pl pair<ll,ll>
#define EPSILON 0.000001

using namespace std;
ifstream fin("dmin.in");
ofstream fout("dmin.out");

const ll N=2e3+5,INF=1e18,MOD=104659,M=1e2+5,inf=INT_MAX;

int n,m;
double dist[N];
int dp[N];
vector<pair<int,double> >adj[N];

void dijkstra()
{
    priority_queue< pair<double,int> >pq;
    for(int i=1;i<=n;i++)
    {
        dist[i]=1e9;
    }
    dp[1]=1;
    pq.push({0,1});
    dist[1]=0;
    while(!pq.empty())
    {
        int a=pq.top().second;
        pq.pop();
        for(int i=0;i<adj[a].size();i++)
        {
            int b=adj[a][i].first;
            double cost=adj[a][i].second;
            if(dist[a]+cost-dist[b]< -EPSILON)
            {
                dp[b]=dp[a];
                dist[b]=dist[a]+cost;
                pq.push({-dist[b],b});
            }
            else if(abs(dist[b]-dist[a]-cost)<EPSILON)
            {
                dp[b]+=dp[a];
                dp[b]%=MOD;
            }
        }
    }
    for(int i=2;i<=n;i++)
    {
        fout<<dp[i]<<" ";
    }
}

int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        fin>>a>>b>>c;
        adj[a].pb({b,log2(c)});
        adj[b].pb({a,log2(c)});
    }
    dijkstra();
}