#include <fstream>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#include <iostream>
using namespace std;

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

const int mod = 104659;
vector<pair<int, long long> > g[1505];
int n, m;
long long dist[1505];
int nrDrumuri[1505];
bool v[1505];

void citire() {
    fin >> n >> m;
    int a, b;
    long long c;
    while(m--) {
        fin >> a >> b >> c;
        g[a].push_back({b,c});
        g[b].push_back({a,c});
    }
}

void dfs(int x) {
    v[x] = 1;
    for(auto next: g[x])
        if(dist[next.first]*next.second == dist[x]) {
            if(!v[next.first])
                dfs(next.first);
            nrDrumuri[x] = (nrDrumuri[x] + nrDrumuri[next.first])%mod;
        }
}

void solve() {
    priority_queue<pair<long long, int > > q;
    q.push({0, 1});
    for(int i = 1; i <= n; i++)
        dist[i] = LLONG_MAX;
    dist[1] = 1;
    while(!q.empty()) {
        int curr = q.top().second;
        q.pop();

        for(auto next: g[curr]) {
            if(dist[next.first] > dist[curr]*next.second) {
                dist[next.first] = dist[curr]*next.second;
                q.push({-dist[next.first], next.first});
            }
        }
    }
    nrDrumuri[1] = 1;
    for(int i = 1; i <= n; i++)
        if(!v[i])
            dfs(i);
    for(int i = 2; i <= n; i++)
        fout << nrDrumuri[i] << ' ';
}

int main() {
    citire();
    solve();
}