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

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

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

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

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

void solve() {
    priority_queue<pair<double, int > > q;
    q.push({0, 1});
    for(int i = 1; i <= n; i++)
        dist[i] = 1000000000.0;
    dist[1] = 0.0;
    nrDrumuri[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) > 1e-8) {
                dist[next.first] = dist[curr]+next.second;
                nrDrumuri[next.first] = nrDrumuri[curr]%mod;
                q.push({-dist[next.first], next.first});
            } else if (abs(dist[next.first] - next.second - dist[curr]) < 1e-8)
                nrDrumuri[next.first] = (nrDrumuri[next.first]+nrDrumuri[curr])%mod;
        }
    }
    for(int i = 2; i <= n; i++)
        fout << nrDrumuri[i] << ' ';
}

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