#include<bits/stdc++.h>
#define MOD 104659
#define maxN 1505
#define INF INT_MAX
using namespace std;
vector<pair<int,double> > v[maxN];
int n,m,x,y,c,seen[maxN];
double cost;
typedef struct SolType
{
  double cost;
  int pos;
};
SolType dp[maxN];
typedef struct edge
{
  int nod;
  double cost;
    bool operator<(const edge& other) const
    {
        return cost>other.cost;
    }
};

priority_queue<edge> q;
void Dijkstra()
{
    int x;
    double y;
    int z;
    while(!q.empty())
    {
        x=q.top().nod;
        y=q.top().cost;
        z=dp[x].pos;
        q.pop();
        if(dp[x].cost<y) continue;
        for(vector<pair<int,double> >::iterator it=v[x].begin();it!=v[x].end();it++)
        {
            double sum=y+(*it).second;
            int t=(*it).first;
            if(sum<dp[t].cost)
            {
                dp[t]={sum,z%MOD};
                q.push({t,dp[t].cost});
            }
                else
            if(sum==dp[t].cost)
            {
                dp[t].pos+=z;
                dp[t].pos%=MOD;
                q.push({t,dp[t].cost});
            }
        }
    }
}
int main()
{
    freopen("dmin.in","r",stdin);
    freopen("dmin.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        cost=log((double)c);
        v[x].push_back(make_pair(y,cost));
        v[y].push_back(make_pair(x,cost));
    }
    dp[1]={0,1};
    for(int i=2;i<=n;i++) dp[i]={1.0*INF,0};
    q.push({1,0});
    Dijkstra();
    for(int i=2;i<=n;i++) printf("%d ",dp[i].pos);
    printf("\n");
}