#include <bits/stdc++.h>

#define EPS 0.000000001

struct smart_long_double {
    smart_long_double(long double val = 0) {this->val = val;}

    long double val;

    smart_long_double& operator = (const smart_long_double& other) {
        val = other.val;
        return *this;
    }
    smart_long_double& operator = (const long double& other) {
        val = other;
        return *this;
    }

    smart_long_double operator + (const smart_long_double& other) {
       return {other.val + this->val};
    }
    smart_long_double operator + (const long double& other) {
       return {other + this->val};
    }

    bool operator > (const smart_long_double& other) const {
        return (val - other.val > EPS);
    }
    bool operator < (const smart_long_double& other) const {
        return (val - other.val < -EPS);
    }
    bool operator == (const smart_long_double& other) const {
        return (abs(other.val - val)) <= EPS;
    }
};  std::ostream& operator << (std::ostream& stream, const smart_long_double& other) {
    stream << other.val;
}

#define int_pair std::pair <int, ldb>
#define djk_pair std::pair <ldb, int>
#define ldb      smart_long_double

#define MAXWEIGHT 1000000005
#define MAXN      1505
#define MOD       104659
#define inf       1000000005

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

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

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

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

void Dijkstra(int Source = 1) {
    for (int i=1; i<=N; ++i)
        Dist[i] = inf;
    Dist[Source] = 0;
    DP[1] = 1;
    PQ.push({{0}, Source});

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

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

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

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

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

    return 0;
}