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

using namespace std;

ifstream cin("dmin.in");
ofstream cout("dmin.out");

int n, m;
const int MOD = 104659;
const double EPS = 1e-12L;
vector<vector<pair<int, int>>> graf;
vector<double> cost;
vector<int> ways;
priority_queue<pair<double, int>, vector<pair<double, int>>, greater<>> pq;
bitset<1505> viz;

inline double loge(long long arg) {
    return ((arg == 0) ? 0 : log(arg));
}

void dijkstra() {
    cost[1] = 0;
    ways[1] = 1;
    pq.push({0, 1});
    while (!pq.empty()) {
        pair<long long, int> current = pq.top();
        pq.pop();
        if (!viz[current.second]) {
            for (pair<int, int> nei : graf[current.second]) {
                if (!viz[nei.first] && cost[current.second] + loge(nei.second) + EPS < cost[nei.first]) {
                    cost[nei.first] = cost[current.second] + loge(nei.second);
                    ways[nei.first] = ways[current.second];
                    pq.push({cost[nei.first], nei.first});
                }
                else if (!viz[nei.first] && fabs(cost[current.second] + loge(nei.second) - cost[nei.first]) <= EPS) {
                    ways[nei.first] += ways[current.second];
                    ways[nei.first] %= MOD;
                }
            }
            viz[current.second] = 1;
        }
    }
}

int main() {
    cin >> n >> m;
    graf.resize(n + 2);
    cost.resize(n + 2, numeric_limits<double>::max());
    ways.resize(n + 2, 0);
    for (int i = 1 ; i <= m ; ++i) {
        int src, dest, cost;
        cin >> src >> dest >> cost;
        graf[src].push_back({dest, cost});
        graf[dest].push_back({src, cost});
    }
    dijkstra();
    for (int i = 2 ; i <= n ; ++i) {
        cout << ways[i] << " ";
    }
    return 0;
}