#include <bits/stdc++.h>
#define MOD 104659
#define EPS 0.0000000001
#define INF 1000000000.0
/// TONI BO$$ was here
/// #MLC

using namespace std;

double dr[1501];
int nrdr[1501];

struct node
{
    int nod;
    double dmin;
    bool operator <(const node &other) const
    {
        return dmin-other.dmin>EPS;
    }
};

struct edge
{
    int nod,en;
};

vector <edge> G[1501];

priority_queue < node > Q;

int main()
{
    int n,m,i,x,y,e,z;
    freopen("dmin.in","r",stdin);
    freopen("dmin.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1; i<=m; i++)
    {
        scanf("%d%d%d",&x,&y,&e);
        G[x].push_back({y,e});
        G[y].push_back({x,e});
    }
    for(i=2; i<=n; i++)
        dr[i]=INF;
    nrdr[1]=1;
    Q.push({1,0.0});
    while(!Q.empty())
    {
        node z=Q.top();
        Q.pop();
        for(auto w : G[z.nod])
            if(abs(dr[w.nod]-z.dmin-log(w.en))<=EPS)
                nrdr[w.nod]=(nrdr[z.nod]+nrdr[w.nod])%MOD;
            else
                if(dr[w.nod]>z.dmin+log(w.en))
                {
                    dr[w.nod]=z.dmin+log(w.en);
                    nrdr[w.nod]=nrdr[z.nod];
                    Q.push({w.nod,dr[w.nod]});
                }
    }
    for(i=2; i<=n; i++)
        printf("%d ",nrdr[i]);

    return 0;
}