/*
Algoritmul lui Dijsktra
Pastram lungimea muchiilor sub forma de logaritmi naturali

*/
#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;

#define NMAX 1502
#define INF (1<<30)
#define MOD 104659
#define EPS 0.0000000001
int n;
int nr[NMAX],viz[NMAX];
double dist[NMAX];

vector <pair<int, double> > v[NMAX];

inline int cmp(double a,double b)
{
    if(a>b+EPS)
        return 1;
    if(a+EPS<b)
        return -1;
    return 0;
}


int main()
{
    freopen("dmin.in","r",stdin);
    freopen("dmin.out","w",stdout);
    int i,j,m,nod,x,y;
    double c,mini;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;++i)
    {
        scanf("%d%d%lf",&x,&y,&c);

        v[x].push_back(make_pair(y,log(c)));
        v[y].push_back(make_pair(x,log(c)));
    }

    for(i=2;i<=n;++i)
        dist[i]=INF;

    nr[1]=1;
   dist[1]=0;

    for(i=1;i<=n;++i)
    {
        mini=INF;
        for(j=1;j<=n;++j)
            if(!viz[j] && dist[j]<mini)
            {
                mini=dist[j];
                nod=j;
            }

        if(cmp(mini,(double)INF)==0)
            break;
        viz[nod]=1;

        for(j=0;j<v[nod].size();++j)
        {
            if(cmp(dist[v[nod][j].first] , dist[nod]+v[nod][j].second)==0)
                nr[v[nod][j].first]=(nr[v[nod][j].first]+nr[nod]) % MOD;
            else if(cmp(dist[v[nod][j].first] , dist[nod]+v[nod][j].second)==1)
            {
                dist[v[nod][j].first]=dist[nod]+v[nod][j].second;
                nr[v[nod][j].first]=nr[nod];
            }
        }

    }

    for(i=2;i<=n;++i)
        printf("%d ",nr[i]%MOD);
    printf("\n");

    return 0;
}