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

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

using namespace std;

ifstream fin("dmin.in");
ofstream fout("dmin.out");

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

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

inline ld vabs(const ld X) {
    return X > 0 ? X : -X;
}

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();

        if(vabs(ccost - dp[cn]) > 0.000001) continue;

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

int main()
{
    fin >> n >> m;
    for(int i = 1; i <= n; ++i)
        dp[i] = INF;
    for(int x, y, z; m; --m) {
        fin >> x >> y >> z;
        ld cost = log2((ld)z);
        adj[x].push_back({cost, y});
        adj[y].push_back({cost, x});
    }
    dij();
    for(int i = 2; i <= n; ++i)
        fout << ans[i] << " ";
    return 0;
}