#include <cstdio>
#include <cmath>

#define inf 1000000000.0
#define maxn 1501
#define eps 0.000000001
#define mod 104659

FILE *in = fopen("dmin.in","r"), *out = fopen("dmin.out","w");

struct graf
{
    int nod;
    double c;

    graf *next;
};

int n, m;
graf *a[maxn] = {NULL};

//dijkstra
double d[maxn];
int nr[maxn];
int q[maxn]; // 1 daca nodul i a fost deja ales

void add(int p, int nod, double cost)
{
    graf *q = new graf;

    q->next = a[p];
    q->nod = nod;
    q->c = cost;
    a[p] = q;
}

void read()
{
    fscanf(in, "%d %d", &n, &m);

    int t1, t2, cst;
    for ( int i = 0; i < m; ++i )
    {
        fscanf(in, "%d %d %d", &t1, &t2, &cst);

        double c = log(cst);

        add(t1, t2, c);
        add(t2, t1, c);
    }
}

int main()
{
    read();

    for ( int i = 2; i <= n; ++i )
        d[i] = inf;
    d[1] = 0.0;
    nr[1] = 1;

    for ( int i = 1; i < n; ++i )
    {
        double min = inf;
        int poz = 0;
        for ( int j = 1; j <= n; ++j )
            if ( min - d[j] >= eps && !q[j] )
                min = d[j], poz = j;
        //printf("%lf\n", min);
        q[poz] = 1;

        graf *q = a[poz];

        while ( q )
        {
            if ( d[q->nod] - (d[poz] + q->c) >= eps)
                d[q->nod] = d[poz] + q->c, nr[q->nod] = nr[poz];
            else if ( fabs((d[poz] + q->c) - d[q->nod]) <= eps )
                nr[q->nod] = (nr[q->nod] + nr[poz]) % mod;

            q = q->next;
        }
    }

    for ( int i = 2; i <= n; ++i )
        fprintf(out, "%d ", nr[i]);

	return 0;
}