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

const int N = 1505;
const int mod = 104659;
int n, m, a, b, c;
vector<pair<int, int>> v[N];
pair<ll, int> d[N]; /// cost, number of ways

struct elem {
    int nod;
    ll 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;
        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].second = 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)
            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) {
                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;
}