#include<fstream>
#include<vector>
#include<cmath>
#include<algorithm>
#include<queue>
#define x first
#define y second

using namespace std;

const char iname[]="dmin.in";
const char oname[]="dmin.out";
const int maxn=1605;
const double inf=1e16;
const int mod=104659;

ifstream f(iname);
ofstream g(oname);

double eps=1e-8,dis[maxn];
inline int cmp(double a,double b)
{
    if(a+eps<b)
        return -1;
    if(b+eps<a)
        return 1;
    return 0;
}

inline bool fcomp(int a,int b)
{
    return dis[a]<dis[b];
}

int n,m,x,y,z,i,been[maxn],pos[maxn],a[maxn];
queue<int> Q;
vector<pair<int,double> > E[maxn];
int main()
{
    f>>n>>m;
    for(i=1;i<=m;++i)
        f>>x>>y>>z,E[x].push_back(make_pair(y,log((double)z))),E[y].push_back(make_pair(x,log((double)z)));
    for(i=1;i<=n;++i)
        dis[i]=inf,been[i]=0;
    dis[1]=0;
    Q.push(1);
    been[1]=1;
    while(!Q.empty())
    {
        x=Q.front();
        Q.pop();
        been[x]=0;
        for(vector<pair<int,double> >::iterator it=E[x].begin();it!=E[x].end();++it)
            if(dis[x]+it->y<dis[it->x])
            {
                dis[it->x]=dis[x]+it->y;
                if(been[it->x]==0)
                    been[it->x]=1,Q.push(it->x);
            }
    }
    for(i=1;i<=n;++i)
        pos[i]=i;
    sort(pos+2,pos+n+1,fcomp);
    a[1]=1;
    for(i=2;i<=n;++i)
        for(vector<pair<int,double> >::iterator it=E[pos[i]].begin();it!=E[pos[i]].end();++it)
            if(cmp(dis[it->x]+it->y,dis[pos[i]])==0)
                a[pos[i]]=(a[pos[i]]+a[it->x])%mod;

    for(i=2;i<=n;++i)
        g<<a[i]<<" ";
    g<<"\n";
}