#include <iostream>
#include <cmath>
#include <vector>
#include <queue>

#define NMAX 1505
#define MOD 104659
#define INF ((1 << 30) - 1)

using namespace std;

typedef long double ld;
typedef pair<ld, int> pldi;

int n, m, dp[NMAX], ans[NMAX];
vector<pldi> adj[NMAX];
priority_queue<pldi, vector<pldi>, greater<pldi> > pq;

void dij() {
    pq.push({0, 1});
    dp[1] = 0;
    ans[1] = 1;
    while(!pq.empty()) {
        const ld ccost = pq.top().first;
        const int cn = pq.top().second;
        pq.pop();

        for(const auto &el : adj[cn]) {
            const ld nccost = el.first;
            const int ncn = el.second;
            if(dp[cn] + nccost < dp[ncn]) {
                dp[ncn] = dp[cn] + nccost;
                ans[ncn] = ans[cn];
                pq.push({dp[ncn], ncn});
            } else if(dp[cn] + nccost == dp[ncn]) {
                ans[ncn] = (ans[ncn] + ans[cn]) % MOD;
            }
        }
    }
}

int main()
{
    freopen("dmin.in", "r", stdin);
    freopen("dmin.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i)
        dp[i] = INF;
    for(int x, y, z; m; --m) {
        scanf("%d%d%d", &x, &y, &z);
        ld cost = log2(z);
        adj[x].push_back({cost, y});
        adj[y].push_back({cost, x});
    }
    dij();
    for(int i = 2; i <= n; ++i)
        printf("%d ", ans[i]);
    return 0;
}