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

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

#define eps 0.0000000001

void dijkstra()
{
    int i,t;
    for (i=1; i<=n; i++) a[i].cost=-1;
    a[1].cost=0; 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-C[i]>eps))
            {
                a[v[2][i]].cost=a[v[1][i]].cost+C[i];
                t=1;
                //printf("%i %f\n",i,a[v[2][i]].cost);
            }
    }
    for (i=1; i<=n; i++) a[i].drum=0; a[1].drum=1;
    for (i=1; i<=m*2; i++)
        if ( abs(a[v[2][i]].cost-a[v[1][i]].cost-C[i])<=eps)
            {
                a[v[2][i]].drum=a[v[2][i]].drum+a[v[1][i]].drum;
            }
}

int main()
{
    int i,c;
    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],&c);
            C[i]=log(c);
            //printf("%f\n",C[i]);
        }
        else{
            v[1][i]=v[2][i-1];
            v[2][i]=v[1][i-1];
            C[i]=C[i-1];
        }
    dijkstra();
    for (i=2; i<=n; i++) printf("%i ",a[i].drum%104659);
    return 0;
}