#include <bits/stdc++.h>
#define cin ci
#define cout co
using namespace std;
ifstream cin("dmin.in");
ofstream cout("dmin.out");
const double INF = 1e18;
const int mod = 104659;
const double eps = 1e-6;
int n, m, x, y, z;
vector<vector<pair<int, double>>> graf;
vector<double> dist;
vector<int> ans, viz;
void djikstra(int node)
{
    priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> q;
    q.push({0.0 ,node});
    dist[node] = 0.0;
    ans[node] = 1;
    while(!q.empty())
    {
        node = q.top().second;
        q.pop();
        if(!viz[node])
        {
            viz[node] = 1;
            for(auto &[next, cost]:graf[node])
                if(dist[next] - dist[node] - cost > eps)
                {
                    dist[next] = dist[node] + cost;
                    q.push({dist[next], next});
                    ans[next] = ans[node];
                }
                else
                    if(fabs(dist[next] - dist[node] - cost) < eps)
                    {
                        q.push({dist[next], next});
                        ans[next] = (ans[next] + ans[node]) % mod;
                    }
        }

    }
}
int main()
{
    cin >> n >> m;
    graf.assign(n+1, vector<pair<int, double>>());
    dist.assign(n+1, INF);
    ans.resize(n+1);
    viz.resize(n+1);
    for(int i=1; i<=m; i++)
    {
        cin >> x >> y >> z;
        double cost = log2(z);
        graf[x].push_back({y, cost});
        graf[y].push_back({x, cost});
    }
    djikstra(1);
    for(int i=2; i<=n; i++)
        cout << ans[i] << " ";
    return 0;
}