#include <bits/stdc++.h>
using namespace std;

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

const int MAX_NUM = 1505;
const int MOD = 104659;
const double eps = 1e-10;

vector<pair<int, double>> graph[MAX_NUM];
vector<double> d(MAX_NUM, DBL_MAX);
vector<int> cnt(MAX_NUM, 0);
bitset<MAX_NUM> visited;
int n, m;

void dijkstra() {
    int start = 1;
    d[start] = 0.0, cnt[start] = 1;
    set<pair<double, int>> dist;
    dist.insert({d[start], start});
    while (!dist.empty()) {
        auto [currentCost, currentNode] = *dist.begin();
        dist.erase(dist.begin());
        if (!visited[currentNode]) {
            visited[currentNode] = true;
            for (auto [node, cost] : graph[currentNode]) {
                if (d[node] > d[currentNode] + cost + eps) {
                    d[node] = d[currentNode] + cost;
                    cnt[node] = cnt[currentNode];
                    dist.insert({d[node], node});
                } else if (abs(d[node] - (d[currentNode] + cost)) < eps) {
                    cnt[node] = (cnt[node] + cnt[currentNode]) % MOD;
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    fin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y;
        double c;
        fin >> x >> y >> c;
        c = log(c);
        graph[x].push_back({y, c});
        graph[y].push_back({x, c});
    }
    dijkstra();
    for (int i = 2; i <= n; ++i) {
        fout << cnt[i] % MOD << " ";
    }
    return 0;
}