#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
FILE*in=fopen("dmin.in","r");
FILE*out=fopen("dmin.out","w");
const int NMAX=1505,MOD=104659,INF=1000000009;
const double inf=0.000001;
int n,m,i,x,y,dp[NMAX],c;
bool b[NMAX];
double d,dijk[NMAX];
struct muc
{
    int nod;
    double cost;
};
muc el;
vector<muc> v[NMAX];
struct mucpl
{
    int nod,tat;
    double cost;
};
mucpl ed;
priority_queue<mucpl> pq;
inline bool operator<(mucpl a,mucpl b)
{
    return a.cost>b.cost;
}
void dij()
{
    while(!pq.empty())
    {
        mucpl ax=pq.top();
        pq.pop();
        if(b[ax.nod]==1)
        {
            if(ax.cost<dijk[ax.nod]+inf&&ax.cost>dijk[ax.nod]-inf)
            {
                dp[ax.nod]+=dp[ax.tat];
                dp[ax.nod]=dp[ax.nod]%MOD;
            }
        }
        else
        {
            b[ax.nod]=1;
            dijk[ax.nod]=(double)(ax.cost);
            dp[ax.nod]=dp[ax.tat];
            for(auto t:v[ax.nod])
            {
                ed.nod=t.nod;
                ed.cost=(double)(t.cost+ax.cost);
                ed.tat=ax.nod;
                pq.push(ed);
            }
        }
    }
}
int main()
{
    memset(dijk,INF,sizeof(dijk));
    fscanf(in,"%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(in,"%d%d%d",&x,&y,&c);
        el.nod=y;
        el.cost=(double)(log(c));
        v[x].push_back(el);
        el.nod=x;
        v[y].push_back(el);
    }
    ed.nod=1;
    ed.cost=0;
    ed.tat=0;
    pq.push(ed);
    dp[0]=1;
    dijk[1]=0;
    dij();
    for(i=2;i<=n;i++)
    {
        fprintf(out,"%d ",dp[i]);
    }
}