#include<fstream>
#include<vector>
#include<cmath>
#include<queue>
#define eps 0.000000001
#define MOD 104659
#define INF  999999999
using namespace std;
ifstream f("dmin.in");
ofstream g("dmin.out");
int i,n,m,x,y11,c,nr[1505],viz[1505];
double d[1505];
struct nod{int x;
double d;};
nod nou,y,nn;
vector<nod>v[1505];
queue<nod>q;
int main()
{
    f>>n>>m;
    for(;m;--m)
    {
        f>>x>>y11>>c;
        nou.x=y11;
        nou.d=(double)log((double)c);
        v[x].push_back(nou);
        nou.x=x;
        v[y11].push_back(nou);
    }
    for(i=2;i<=n;++i)
    d[i]=INF;
    nr[1]=1;
    nou.x=1;
    nou.d=0;
    q.push(nou);
    viz[1]=1;
    while(!q.empty())
    {
        nou=q.front();
        q.pop();
        viz[nou.x]=0;
        for(i=0;i<v[nou.x].size();++i)
        {
            y=v[nou.x][i];
            if(d[y.x]-nou.d-y.d>eps)
            {
                d[y.x]=y.d+nou.d;
                nr[y.x]=nr[nou.x];
                if(!viz[y.x])
                {
                    nn.x=y.x;
                    nn.d=d[y.x];
                    q.push(nn);
                    viz[y.x]=1;
                }
            }
            else
            if(abs(d[y.x]-nou.d-y.d)<eps)
            nr[y.x]=(nr[y.x]+nr[nou.x])%MOD;
        }
    }
    for(i=2;i<=n;++i)
    g<<nr[i]<<' ';
    return 0;
}