#include <cstdio>
#include <queue>
#include <cmath>
#include <vector>

#define NMAX 1501
#define INF 1000000000
#define MOD 104659

using namespace std;

int N, M;
queue<int> q;
double d[NMAX], eps = 1e-10;
int sol[NMAX], inqueue[NMAX];
vector<vector<pair<int, double> > > v(NMAX);

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

    scanf("%d %d", &N, &M);

    for(int i=0;i<M;++i)
    {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);

        v[a].push_back(make_pair(b, log(c)));
        v[b].push_back(make_pair(a, log(c)));
    }

    for(int i=2;i<=N;++i)
    {
        d[i] = INF;
    }

    d[1] = 0;
    sol[1] = 1;
    q.push(1);
    inqueue[1] = 1;

    while(!q.empty())
    {
        int current = q.front();
        q.pop();

        inqueue[current] = 0;


        for(int i=0;i<v[current].size();++i)
        {
            if(fabs(d[v[current][i].first] - d[current] - v[current][i].second) < eps)
            {
                sol[v[current][i].first] += sol[current];
                if(sol[v[current][i].first] > MOD)
                {
                    sol[v[current][i].first] %= MOD;
                }
                if(!inqueue[v[current][i].first])
                {
                    q.push(v[current][i].first);
                    inqueue[v[current][i].first] = 1;
                }
            }
            if(d[v[current][i].first] - d[current] - v[current][i].second > eps)
            {
                d[v[current][i].first] = d[current] + v[current][i].second;
                sol[v[current][i].first] = sol[current];
                if(!inqueue[v[current][i].first])
                {
                    q.push(v[current][i].first);
                    inqueue[v[current][i].first] = 1;
                }
            }
        }
    }

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

    return 0;
}