#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#define MOD 104659
#define FICAT 1501
using namespace std;

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

vector<vector <pair<int, long long> > > V;
queue<int> Q;
int n, m;
long long x, y, cost;
long long d[FICAT];
int cnt[FICAT];

int main()
{
    is >> n >> m;
    V.resize(n+1);
    for (int i = 1; i <= m; ++i)
    {
        is >> x >> y >> cost;
        V[x].push_back(make_pair(y, cost));
        V[y].push_back(make_pair(x, cost));
    }

    memset( d, 63, sizeof(d));

    Q.push(1);
    d[1] = 1;
    cnt[1] = 1;
    while (!Q.empty())
    {
        x = Q.front();
        Q.pop();
        for (int i = 0; i < V[x].size(); ++i)
        {
            cost = d[x] * V[x][i].second % MOD;
            y = V[x][i].first;
            if (cost == d[y])
            {
                cnt[y]++;
                Q.push(y);
            }

            if (cost < d[y])
            {
                cnt[y] = 1;
                d[y] = cost;
                Q.push(y);
            }

        }
    }

    for (int i = 1; i <= n; ++i)
        os << cnt[i]  << ' ';


    is.close();
    os.close();
    return 0;
}