#include <bits/stdc++.h>
#define DM 1505
#define pb push_back
#define piii pair<int,pair<int,int> >
#define x first
#define y second
#define INF 0x3f3f3f3f
#define MOD 104659
using namespace std;
ifstream fin("dmin.in");
ofstream fout("dmin.out");

struct mch{int fiu,cst;};
vector<mch>G[DM];
priority_queue<piii,vector<piii>, greater<piii> >Q;
bitset<DM>viz;
int ans[DM],mnCost[DM],timesInQueue[DM],a,b,c,n,m;

int main()
{
    fin>>n>>m;
    while(m--){
        fin>>a>>b>>c;
        G[a].pb({b,c});
    }
    memset(mnCost,INF,sizeof(mnCost));
    Q.push({1,{1,1}});
    ans[1]=1;
    timesInQueue[1]=1;

    while(!Q.empty()){
        int nod = Q.top().y.x;
        int tata = Q.top().y.y;
        int cst = Q.top().x;
        Q.pop(),timesInQueue[nod]--;

        if(cst > mnCost[nod]) continue;
        if(cst == mnCost[nod]){
            ans[nod]+=ans[tata],ans[nod]%=MOD;
        }
        if(cst < mnCost[nod]) mnCost[nod]=cst,ans[nod]=ans[tata];

        if(!timesInQueue[nod]){
            for(auto i:G[nod])
                Q.push({cst*i.cst,{i.fiu,nod}}), timesInQueue[i.fiu]++;
        }

    }
    for(int i=2;i<=n;++i) fout<<ans[i]<<" ";
    return 0;
}