#include <bits/stdc++.h>

#define int long long

using namespace std;

ifstream fin("dmin.in");
ofstream fout("dmin.out");

const int MOD = 104659;

int n, m;
int dp[1515]; /// numarul de moduri de a ajunge cu distanta minima la nodul i
struct elem
{
    int nod, cost;
    bool operator < (const elem other) const
    {
        return cost > other.cost;
    }
};
vector<elem> v[1515];
priority_queue<elem> coada;
int ans[1515];

void Dijkstra()
{
    coada.push({1,1});
    dp[1] = 1;
    while(!coada.empty())
    {
        int nod = coada.top().nod;
        int cost = coada.top().cost;
        ///fout << "intre nodul 1 si nodul " << nod << " avem " << dp[nod] << " drumuri minime de cost " << cost;
        coada.pop();
        if(cost != ans[nod])
            continue;
        for(auto it : v[nod])
        {
            if(cost * it.cost < ans[it.nod])
            {
                ans[it.nod] = cost * it.cost;
                dp[it.nod] += dp[nod];
                dp[it.nod] %= MOD;
                coada.push({it.nod, ans[it.nod]});
            }
            else
            {
                if(cost * it.cost == ans[it.nod])
                {
                    dp[it.nod] += dp[nod];
                    dp[it.nod] %= MOD;
                }
            }
        }
    }
}

int32_t main()
{
    fin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        ans[i] = LLONG_MAX;
    }
    ans[1] = 1;
    while(m--)
    {
        int a, b, c;
        fin >> a >> b >> c;
        v[a].push_back({b,c});
        v[b].push_back({a,c});
    }

    Dijkstra();

    for(int i = 2; i <= n; i ++)
    {
        fout << dp[i] << ' ';
    }
    fout << '\n';
    return 0;

}