#include <bits/stdc++.h>
#define PDI pair <double, int>
#define DIM 1505
#define MOD 104659

using namespace std;

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

int n, m, nr[DIM];
double d[DIM];
vector <pair <int, double>> edges[DIM];
priority_queue <PDI, vector <PDI>, greater <PDI>> pq;

void dijkstra()
{
    for(int i = 1; i <= n; i++)
        d[i] = 0x3f3f3f3f;
    d[1] = 0;
    nr[1] = 1;
    pq.push({0, 1});
    while(!pq.empty())
    {
        int nod = pq.top().second;
        double cost = pq.top().first;
        pq.pop();
        if(cost != d[nod])
            continue;
        for(auto child : edges[nod])
            if(d[child.first] > d[nod] + child.second)
            {
                nr[child.first] = nr[nod];
                d[child.first] = d[nod] + child.second;
                pq.push({d[child.first], child.first});
            }
            else if(d[child.first] == d[nod] + child.second)
            {
                nr[child.first] += nr[nod];
            }

    }
}


int main()
{
    f >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int x, y, c;
        f >> x >> y >> c;
        c %= MOD;
        edges[x].push_back({y, log(c)});
        edges[y].push_back({x, log(c)});
    }
    dijkstra();

    for(int i = 2; i <= n; i++)
        g << nr[i] << " ";

    return 0;
}