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

const int N = 1505;
const int mod = 104659;
int n, m, a, b;
ld eps = 1e-18;
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 = log2(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;
        ll cost = top.cost;
        if (cost - d[nod].first > eps)
            continue;
        for (auto e : v[nod]) {
            if (d[nod].first + e.second < d[e.first].first) {
                d[e.first].first = d[nod].first + e.second;
                d[e.first].second = d[nod].second;
                q.push({e.first, d[e.first].first});
            } else if (d[nod].first + e.second - 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;
}