#include <bits/stdc++.h>

std :: ifstream in ("dmin.in");

std :: ofstream out ("dmin.out");

const int NMAX = 15e2 + 5;

const long long INF = 1e18L;

const int mod = 104659;

const double EPS = 0.000001;

int n;

int m;

int x;

int y;

double d;

double dist[NMAX];

int dp[NMAX];

std :: vector <std :: pair<int, double>> v[NMAX];

std :: bitset <NMAX> visited;

std :: priority_queue <std :: pair<double, int>> pq;

void dijkstra()
{
    while(!pq.empty())
    {
        int nod = pq.top().second;

        pq.pop();

        if(visited[nod] == false)
        {
            visited[nod] = true;

            for(auto i : v[nod])
            {
                if(1.00 * dist[nod] + i.second < 1.00 * dist[i.first])
                {
                    dist[i.first] = dist[nod] + i.second;

                    dp[i.first] = dp[nod];

                    pq.push(std :: make_pair(-dist[i.first], i.first));
                }
                else if(1.00 * abs(1.00 * dist[nod] + i.second - dist[i.first]) < EPS)
                {
                    dp[i.first] += dp[nod];

                    dp[i.first] %= mod;
                }
            }
        }
    }
}

int main()
{

    in >> n >> m;

    for(int i = 1; i <= m; i ++)
    {
        in >> x >> y >> d;

        d = log(d);

        v[x].push_back(std :: make_pair(y, d));

        v[y].push_back(std :: make_pair(x, d));
    }

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

    dist[1] = 0;

    dp[1] = 1;

    pq.push(std :: make_pair(0, 1));

    dijkstra();

    for(int i = 2; i <= n; i ++)
    {
        out << dp[i] % mod << " ";
    }

    return 0;
}