#include <bits/stdc++.h>
using namespace std;
ifstream fcin("dmin.in");
ofstream fcout("dmin.out");
typedef long double ld;

const int N = 1505;
const int mod = 104659;
int n, m, a, b;
ld eps = 1e-10;
ld c;
vector<pair<int, ld>> v[N];
pair<ld, int> d[N]; /// cost, number of ways

struct elem {
    int nod;
    ld cost;
    bool operator < (const elem &x) const {
        return cost > x.cost;
    }
};
priority_queue<elem> q;

int main() {
    fcin >> n >> m;
    while (m--) {
        fcin >> a >> b >> c;
        c = log(c);
        v[a].push_back({b, c});
        v[b].push_back({a, c});
    }
    for (int i = 2; i <= n; i++)
        d[i].first = 1e18;
    d[1] = {0, 1};
    q.push({1, 0});
    while (!q.empty()) {
        auto top = q.top();
        q.pop();
        int nod = top.nod;
        ld cost = top.cost;
        if (abs(cost - d[nod].first) > eps)
            continue;
        for (auto e : v[nod]) {
            ld new_cost = cost + e.second;
            if (new_cost < d[e.first].first - eps) {
                d[e.first].first = new_cost;
                d[e.first].second = d[nod].second;
                q.push({e.first, new_cost});
            }
            else if (abs(new_cost - d[e.first].first) < eps) {
                d[e.first].second = (d[e.first].second + d[nod].second) % mod;
            }
        }
    }
    for (int i = 2; i <= n; i++)
        fcout << d[i].second << ' ';
    fcin.close();
    fcout.close();
    return 0;
}