#include <iostream>
#include <stdio.h>
using namespace std;

int v[4][5010];
int n,m;
struct s{
    double cost;
    int drum;
} a[1510];

void dijkstra()
{
    int i,t;
    for (i=1; i<=n; i++) a[i].cost=-1;
    a[1].cost=1; a[1].drum=1; t=1;
    while (t)
    {
        t=0;
        for (i=1; i<=m*2; i++)
            if (a[v[1][i]].cost!=-1 && (a[v[2][i]].cost==-1 || a[v[2][i]].cost>a[v[1][i]].cost*v[3][i]))
            {
                a[v[2][i]].cost=a[v[1][i]].cost*v[3][i];
                t=1;
                a[v[2][i]].drum=a[v[1][i]].drum;
            }
    }

    for (i=1; i<=n; i++) a[i].drum=0; a[1].drum=1;
    for (i=1; i<=m*2; i++)
        if ( a[v[1][i]].cost!=-1 && a[v[2][i]].cost==a[v[1][i]].cost*v[3][i])
            {
                a[v[2][i]].drum=(a[v[2][i]].drum+a[v[1][i]].drum)%104659;
            }
}

int main()
{
    int i;
    freopen("dmin.in","r",stdin);
    freopen("dmin.out","w",stdout);
    scanf("%i%i",&n,&m);
    for (i=1; i<=m*2; i++)
        if (i%2==1) scanf("%i%i%i",&v[1][i],&v[2][i],&v[3][i]);
        else{
            v[1][i]=v[2][i-1];
            v[2][i]=v[1][i-1];
            v[3][i]=v[3][i-1];
        }
    dijkstra();
    for (i=2; i<=n; i++) printf("%i ",a[i].drum);
    return 0;
}