#include <cmath>
#include <cstdio>

#include <queue>
#include <vector>

#define NMAX 1510
#define MOD 104659

using std::vector;
using std::priority_queue;

struct Arc {
    int node;
    int cost;
};

inline bool operator<(Arc x, Arc y) {
    return x.cost > y.cost;
}

int n, m;
vector<Arc> ad[NMAX];

int nr[NMAX];
double dp[NMAX];

bool onPQ[NMAX];
priority_queue<Arc> pq;

inline bool equals(double x, double y) {
    return (x < y ? y - x : x - y) < 0.000001;
}

int main() {
    int a, b, c;
    freopen("dmin.in", "r", stdin);
    freopen("dmin.out", "w", stdout);

    scanf("%d %d\n", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d %d %d\n", &a, &b, &c);
        ad[a].push_back({b, c});
        ad[b].push_back({a, c});

        if (a == 1)
            nr[b] = 1;
        else if (b == 1)
            nr[a] = 1;
    }

    pq.push({1, 0});
    onPQ[1] = true;

    while (!pq.empty()) {
        int node = pq.top().node;
        pq.pop();
        onPQ[node] = false;

        for (Arc arc : ad[node]) {
            double cost = dp[node] + log10(arc.cost);
            if (equals(dp[arc.node], 0) || (cost < dp[arc.node] || equals(cost, dp[arc.node]))) {
                dp[arc.node] = cost;
                if (equals(cost, dp[arc.node]))
                    nr[arc.node] = (nr[arc.node] + nr[node]) % MOD;
                else
                    nr[arc.node] = nr[node];

                if (!onPQ[arc.node]) {
                    pq.push({arc.node, dp[arc.node]});
                    onPQ[arc.node] = true;
                }
            }
        }
    }

    for (int i = 2; i <= n; i++)
        printf("%d ", nr[i]);
    printf("\n");

    fclose(stdout);
    return 0;
}