#include<cstdio>
#include<cmath>
#define MOD 104659
#define eps 1e-10
using namespace std;

typedef struct Nod {
    int nod;
    double cost;
    Nod *urm;
} NOD;

NOD *v[1505], *q, *p;
int x, y, i, j, n, m, nod0, viz[1505];
double c, d[1505];
long long nr[1505];

int egal(double a, double b) {
    if (fabs(a-b)<eps) return 1;
    else return 0;
}

void dijkstra(int x0) {
    p=v[x0];
    while (p->urm != NULL) {
        d[p->nod]=p->cost;
        p=p->urm;
    }

    d[x0]=0; nr[x0]=1;

    for (j=1; j<n; ++j) {
        double min=1000000005;
        for (i=1; i<=n; ++i) {
            if (viz[i]==0 && min>d[i]) { min=d[i]; nod0=i; }
        }

        viz[nod0]=1;
        p=v[nod0];
        while (p->urm != NULL) {
            if (d[p->nod] - min - p->cost > eps) { d[p->nod]=min+p->cost, nr[p->nod]=nr[nod0]; }
            else if ( egal(d[p->nod], min+p->cost) ) { nr[p->nod]=(nr[p->nod]+nr[nod0])%MOD; }
            p=p->urm;
        }
    }

}

int main () {
    freopen("dmin.in", "r", stdin);
    freopen("dmin.out", "w", stdout);
    scanf("%d %d", &n, &m);

    for (i=1; i<=n; ++i) {
        v[i]=new NOD;
        v[i]->cost=1000000005.;
        v[i]->nod=1600;
        v[i]->urm=NULL;

        d[i]=1000000000.;
    }

    for (i=1; i<=m; ++i) {
        scanf("%d %d %f", &x, &y, &c);

        q=new NOD;
        q->cost=log10(c);
        q->nod=y;
        q->urm=v[x];
        v[x]=q;

        q=new NOD;
        q->cost=log10(c);
        q->nod=x;
        q->urm=v[y];
        v[y]=q;
    }

    dijkstra(1);

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

    return 0;
}