#include <fstream>
#include <vector>
#include <queue>
#include <cmath>

using namespace std;

ifstream f("dmin.in");
ofstream g("dmin.out");

#define NMAX 1505
#define INF ((1<<30)-1)
#define MOD 104659
#define TIP pair<long double,int>
#define MARJA 0.000001

int n, m, ct[NMAX];
long double d[NMAX];
vector<pair<int, int>> G[NMAX];
priority_queue<TIP, vector<TIP >, greater<>> q;

void citire() {
    f >> n >> m;
    int x, y, t;
    for (int i = 1; i <= m; ++i) {
        f >> x >> y >> t;
        long double cost = log2((long double) t);
        G[x].push_back({cost, y});
        G[y].push_back({cost, x});
    }
}

void initializare() {
    d[1] = 0;
    ct[1] = 1;
    for (int x = 2; x <= n; ++x)
        d[x] = INF;
    q.push({0, 1});
}

void actualizare_nod(int nod, long double valnoua) {
    d[nod] = valnoua;
    q.push({d[nod], nod});
}

void vizitare_nod(int x, long double valoare) {
    if (abs(valoare - d[x]) > MARJA)
        return;
    for (auto &nod: G[x]) {
        if (d[nod.second] > d[x] + nod.first + MARJA) {
            actualizare_nod(nod.second, d[x] + nod.first);
            ct[nod.second] = ct[x];
        } else if (abs(d[x] + nod.first - d[nod.second]) < MARJA)
            ct[nod.second] = (ct[nod.second] + ct[x]) % MOD;
    }
}

void dijkstra() {
    while (!q.empty()) {
        TIP nod = q.top();
        q.pop();
        vizitare_nod(nod.second, nod.first);
    }
}

void afisare() {
    for (int i = 2; i <= n; ++i)
        g << ct[i] << ' ';
}

int main() {
    citire();
    initializare();
    dijkstra();
    afisare();
    return 0;
}