#include <bits/stdc++.h>

using namespace std;

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

int n, m;

vector <pair <int, int>> g[1501];

int fre[1501], dist[1501], cnt[1501];

struct compara
{
    bool operator()(int l, int c)
    {
        return dist[l] > dist[c];
    }
};
const int mod = 104659;
priority_queue <int, vector <int>, compara> pq;

void dijkstra()
{
    while(!pq.empty())
    {
        int curent = pq.top();
        pq.pop();
        fre[curent] = 0;
        //out << curent << '\n';
        for(int i = 0; i < g[curent].size(); i++)
        {

            int vecin = g[curent][i].first;
            int cost = g[curent][i].second;
            if((dist[curent] * cost) % mod == dist[vecin])
            {
                cnt[vecin] += cnt[curent];
            }
            if((dist[curent] * cost) % mod  < dist[vecin])
            {
                dist[vecin] = (dist[curent] * cost) % mod;
                cnt[vecin] = cnt[curent];
                if(fre[vecin] == 0)
                {
                    pq.push(vecin);
                    fre[vecin] = 1;
                }
            }
        }
    }
}

int main()
{
    in >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int x, y, cost;
        in >> x >> y >> cost;
        g[x].push_back({y, cost});
        g[y].push_back({x, cost});
    }
     for(int i = 1; i <= n; i++)
    {
        dist[i] = INT_MAX;
    }
    dist[1] = 1;
    pq.push(1);
    fre[1] = 1;
    cnt[1] = 1;
    dijkstra();
    for(int i = 2; i <= n; i++)
        out << cnt[i] << ' ';
    return 0;
}