#include <bits/stdc++.h>

#define int_pair std::pair <int, int>
#define djk_pair std::pair <llg, int>
#define llg      long long

#define MAXWEIGHT 1000000005
#define MAXN      1505
#define MOD       104659
const llg inf = MAXWEIGHT * MAXN;

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

inline void AddEdge(int x, int y, int 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;
std::vector <int> Order;
llg Dist[MAXN];

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

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

        if (Top.first > Dist[Top.second]) continue;
        Order.push_back(Top.second);

        for (auto Edge:ADC[Top.second])
            if (Dist[Edge.first] > Dist[Top.second] + 1LL * Edge.second)
                Dist[Edge.first] = Dist[Top.second] + 1LL * Edge.second,
                PQ.push({Dist[Edge.first], Edge.first});
    }
}

int DP[MAXN];
void Dyn() {
    DP[1] = 1;
    for (int i=1; i<Order.size(); ++i)
        for (auto Edge:ADC[Order[i]])
            if (Dist[Edge.first] + 1LL * Edge.second == Dist[Order[i]])
                DP[Order[i]] = (DP[Order[i]] + 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, w);
}

void Rezolvare() {
    Dijkstra();
    Dyn();

    for (int i=1; i<=N; ++i)
        Out << DP[i] << ' ' ;
}

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

    return 0;
}