#include <bits/stdc++.h>

#define ldb long double
#define data_pair std::pair <ldb, int>

#define MAXN 1505
#define MOD  104659

int N, M;
std::vector <data_pair> ADC[MAXN];

inline void AddEdge(int x, int y, ldb w) {
    ADC[x].push_back({log(w), y});
    ADC[y].push_back({log(w), x});
}

bool Equal(ldb x, ldb y) {
    return std::abs(x-y) < 1e-9L;
}

std::ifstream In("dmin.in");
std::ofstream Out("dmin.out");

std::priority_queue <data_pair, std::vector <data_pair>, std::greater <data_pair>> PQ;
ldb Dist[MAXN];
int DP[MAXN];

void Dijkstra() {
    for (int i=1; i<=N; ++i)
        Dist[i] = std::numeric_limits<ldb>::infinity();
    Dist[1] = 0;
    DP[1] = 1;
    PQ.push({0, 1});

    data_pair Top;
    while (!PQ.empty()) {
        Top = PQ.top();
        PQ.pop();

        if (!Equal(Top.first, Dist[Top.second])) continue;
        for (auto Edge:ADC[Top.second]) {
            if (Equal(Dist[Edge.second], Dist[Top.second] + Edge.first))
                DP[Edge.second] += DP[Top.second];
            else if (Dist[Edge.second] > Dist[Top.second] + Edge.first)
                Dist[Edge.second] = Dist[Top.second] + Edge.first,
                DP[Edge.second] = DP[Top.second],
                PQ.push({Dist[Edge.second], Edge.second});

            DP[Edge.second] %= MOD;
        }
    }
}

void Citire() {
    In >> N >> M;
    for (int i=0, x, y, w; i<M; ++i)
        In >> x >> y >> w, AddEdge(x, y, (ldb)(w));
}

void Rezolvare() {
    Dijkstra();
    for (int i=2; i<=N; ++i)
        Out << DP[i] << ' ';
}

int main()
{
    Citire();
    Rezolvare();

    return 0; }