#include<cstdio>
#define MOD 104659
using namespace std;

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

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

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) {
        min=1000005;
        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) { d[p->nod]=min+p->cost, nr[p->nod]=nr[nod0]; }
            else if (d[p->nod]==min+p->cost) { nr[p->nod]+=nr[nod0]; }
            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=1000000;
        v[i]->nod=1600;
        v[i]->urm=NULL;

        d[i]=1000000;
    }

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

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

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

    dijkstra(1);

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

    return 0;
}