#include <bits/stdc++.h>
#define INF 1e18
#define MOD 104659

using namespace std;
using PA = pair<double, int>;

const double errorMargin = 1e-9; // marja de eroare pt calculele cu log

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

int n, m;
double d[1505];
int drumuri[1505];
vector<pair<int, int>> G[1505];
priority_queue<PA, vector<PA>, greater<PA>> PQ;

void dijkstra() {
    for (int i = 1; i <= n; i++) {
        d[i] = INF;  
        drumuri[i] = 0;
    }
    // Aparent costurile se determina prin inmultiri la problema aceasta
    // Deci, ca sa transformam inmultirile in adunari, folosim logaritm
    d[1] = 0;
    drumuri[1] = 1;
    PQ.push({0, 1});  // (cost logaritmic, nod)

    while (!PQ.empty()) {
        double x = PQ.top().first;
        int y = PQ.top().second;
        PQ.pop();

        if (x > d[y] + errorMargin) {
            continue;
        }

        for (auto i : G[y]) {
            int vecin = i.first;
            double logCost = log2(i.second);

            if (d[y] + logCost < d[vecin] - errorMargin) {
                d[vecin] = d[y] + logCost;
                drumuri[vecin] = drumuri[y];
                PQ.push({d[vecin], vecin});
            } else if (fabs(d[y] + logCost - d[vecin]) <= errorMargin) {
                drumuri[vecin] = (drumuri[vecin] + drumuri[y]) % MOD;
            }
        }
    }
}

int main() {
    fin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int x, y, z;
        fin >> x >> y >> z;
        G[x].push_back({y, z});
        G[y].push_back({x, z});
    }

    dijkstra();

    for (int i = 2; i <= n; ++i) {
        fout << drumuri[i] << " ";
    }
    return 0;
}