#include<bits/stdc++.h>
#define MOD 104659
#define maxN 1505
#define INF INT_MAX
#define eps 0.001
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;
  int pos;
    bool operator<(const edge& other) const
    {
        return cost>other.cost;
    }
};
priority_queue<edge> q;
bool egal(double a,double b)
{
    double dif=a-b;
    if(dif<0) dif=-dif;
    if(dif<eps) return 1;
    return 0;
}
void Dijkstra()
{
    int x;
    double y;
    int z;
    while(!q.empty())
    {
        x=q.top().nod;
        y=q.top().cost;
        z=q.top().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,dp[t].pos});
            }
                else
            if(egal(sum,dp[t].cost))
            {
                dp[t].pos+=z;
                dp[t].pos%=MOD;
                q.push({t,dp[t].cost,dp[t].pos});
            }
        }
    }
}
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,1});
    Dijkstra();
    for(int i=2;i<=n;i++) printf("%d ",dp[i].pos%MOD);
    printf("\n");
}