#include <bits/stdc++.h>
#define N 1505
#define MOD 104659
#define INF 0x3f3f3f3f
#define EPS 1e-9
using namespace std;
ifstream fin("dmin.in");
ofstream fout("dmin.out");
struct muchie
{
    int nod;
    double cost;
    bool operator < (const muchie x) const
    {
        return x.cost<cost;
    }
};
double d[N];
int nr[N],n,m;
vector<muchie>g[N];
priority_queue<muchie>pq;
void Dijkstra()
{
    pq.push({1,0});
    fill(d+2,d+n+1,INF);
    nr[1]=1;
    while(!pq.empty())
    {
        int nod=pq.top().nod;
        double cost=pq.top().cost;
        pq.pop();///cout<<cost<<"\n";
        if(-d[nod]+cost>EPS) continue;
        for(auto i:g[nod])
            if(-i.cost-d[nod]+d[i.nod]>EPS)
              d[i.nod]=i.cost+d[nod],nr[i.nod]=nr[nod],pq.push({i.nod,i.cost+d[nod]});
            else if(abs(d[i.nod]-i.cost-d[nod])<EPS) nr[i.nod]+=nr[nod],nr[i.nod]%=MOD;
    }
}
int main()
{
    int i,x,y;
    double c;
    fin>>n>>m;
    while(m--) fin>>x>>y>>c,c=log2(c),g[x].push_back({y,c}),g[y].push_back({x,c});
    Dijkstra();
    for(i=1;i<n;i++) fout<<nr[i+1]<<" ";
    return 0;
}