#include <fstream>
#include <vector>
#include <queue>
#include <climits>
#include <cmath>

using namespace std;

///Problema nu vrea suma, ci produs de costuri si atunci logaritmam in baza 2 totul ca atunci cand le adunam sa ne dea exponentul produsului de fapt.

const int NMAX = 1500;
const int MODULO = 104659;

const double EPSILON = 0.0000000001;

vector<pair<double, int>> graf[1 + NMAX];

long long sol[1 + NMAX];
double cost[1 + NMAX];

priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> pq;

int comp(double a, double b) ///Returneaza -1 pentru a < b, 0 pentru a = b si 1 pentru a > b.
{
    if (b - a > EPSILON)
        return -1;
    else if (a - b > EPSILON)
        return 1;
    else
        return 0;
}

void dijkstra(int nod)
{
    sol[nod] = 1;
    cost[nod] = 0;

    pq.emplace(cost[nod], nod);

    while (!pq.empty())
    {
        int nod_ = pq.top().second;
        double cost_ = pq.top().first;
        pq.pop();

        if (comp(cost_, cost[nod_]) == 1)
            continue;

        for (int i = 0; i < graf[nod_].size(); i++)
        {
            int vecin = graf[nod_][i].second;
            double costMuchieVecin = graf[nod_][i].first;

            if (comp(cost_ + costMuchieVecin, cost[vecin]) == -1)
            {
                sol[vecin] = sol[nod_];
                cost[vecin] = cost_ + costMuchieVecin;
                pq.emplace(cost_ + costMuchieVecin, vecin);
            }
            else if (comp(cost_ + costMuchieVecin, cost[vecin]) == 0)
            {
                sol[vecin] += sol[nod_];
                sol[vecin] %= MODULO;
            }
        }
    }
}

int main()
{
    ifstream in("dmin.in");
    ofstream out("dmin.out");

    int n, m;
    in >> n >> m;

    for (int i = 1; i <= m; i++)
    {
        int x, y;
        long long c;

        in >> x >> y >> c;

        double logC = log2(c);

        graf[x].emplace_back(logC, y);
        graf[y].emplace_back(logC, x);
    }

    for (int i = 2; i <= n; i++)
        cost[i] = INT_MAX;

    dijkstra(1);

    for (int i = 2; i <= n; i++)
        out << sol[i] << ' ';
    out << '\n';

    return 0;
}