#include <bits/stdc++.h>

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

#define MAXN 1505
#define MOD  104659
#define EPS  1e-9L

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

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

bool Equal(lld x, lld y) {
    return abs(x-y) < EPS;
}

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

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

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

    dijk_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.first], Dist[Top.second] + Edge.second))
                DP[Edge.first] += DP[Top.second];
            else 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});
            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, log((long double)(w)));
}

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

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

    return 0;
}