#include <stdio.h>
#include <math.h>

#define NMAX 1503
#define INF 2000000000
#define MOD 104659
#define eps 0.000000001
#define eps2 0.000000000001

double a[NMAX][NMAX];
int uz[NMAX];
int n, m;
double dist[NMAX];
int nr[NMAX];

void read()
{
        int i, j;
        int x, y, z;
        scanf("%d %d", &n, &m);

        for(i = 1; i <= n; ++i)
        {
                dist[i] = INF;
                for(j = 1; j <= n; ++j)
                        a[i][j] = a[j][i] = INF;
        }

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

                a[x][y] = a[y][x] = log(z);

                if(x == 1 || y == 1)
                        dist[ x != 1 ? x : y ] = a[x][y], ++nr[ x != 1 ? x : y];
        }
}
inline int egal(double a, double b)
{
        if(floor(a) != floor(b))
                return 0;
        a -= floor(a);
        b -= floor(b);

        if(a - b > eps2)
                return 0;
        return 1;
}

void dijkstra()
{
        int i, j, pozmin;
        double min;

        ++uz[1];

        for(i = 0; i < n-1; ++i)
        {
                for(min = INF, j = 2; j <= n; ++j)
                {
                        if(!uz[j] && dist[j] < min)
                        {
                                min = dist[j];
                                pozmin = j;
                        }
                }

               for(++uz[pozmin], j = 2; j <= n; ++j)
                {
                        if(!uz[j] && a[pozmin][j] != INF && j != pozmin)
                        {
                                if(dist[j] - dist[pozmin] - a[pozmin][j] > eps2)
                                        nr[j] = nr[pozmin], dist[j] = dist[pozmin] + a[pozmin][j];

                                else if(dist[j] - (dist[pozmin] + a[pozmin][j]) < eps2)
                                        nr[j] += nr[pozmin], nr[j] %= MOD;
                        }
                }
        }
}

int main()
{
        freopen("dmin.in", "r", stdin);
        freopen("dmin.out", "w", stdout);

        read();

        dijkstra();

        int i;
        for(i = 2; i <= n; ++i)
        {
                printf("%d ", nr[i]);
        }
        printf("\n");

        fclose(stdin);
        fclose(stdout);

        return 0;
}