#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;
using ld = long double;

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

const int mod = 104659;
const int NMAX = 2048;
int N, M;
pair<ld,int> dp[NMAX];
vector<pair<int,ld>> G[NMAX];
priority_queue<pair<ld,int>> Q;

void add_self(int &a, int b) {
    a += b;
    if(a >= mod)
        a -= mod;
}

void Dijkstra() {
    for(int u = 1; u <= N; ++u)
        dp[u].first = INF;
    dp[1] = make_pair(0, 1);
    Q.emplace(0, 1);
    while(!Q.empty()) {
        int u = Q.top().second,
            d = -Q.top().first;
        Q.pop();
        for(const auto &v : G[u])
            if(dp[v.first].first > dp[u].first + v.second) {
                dp[v.first].first = dp[u].first + v.second;
                dp[v.first].second = dp[u].second;
                Q.emplace(-dp[v.first].first, v.first);
            }
            else
                if(dp[v.first].first == dp[u].first + v.second)
                    add_self(dp[v.first].second, dp[u].second);
    }
}

int main() {
    fin >> N >> M;
    for(int i = 0; i < M; ++i) {
        int u, v;
        ld w;
        fin >> u >> v >> w;
        w = log2(w);
        G[u].emplace_back(v, w);
        G[v].emplace_back(u, w);
    }
    Dijkstra();
    for(int u = 1; u <= N; ++u)
        fout << dp[u].second << ' ';
    fout << '\n';
}