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

using namespace std;

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

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

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

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

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

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

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

        if (cost_ > cost[nod_])
            continue;

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

            if (cost_ + costMuchieVecin < cost[vecin])
            {
                sol[vecin] = sol[nod_];
                cost[vecin] = cost_ + costMuchieVecin;
                pq.emplace(cost_ + costMuchieVecin, vecin);
            }
            else if (cost_ + costMuchieVecin == cost[vecin])
            {
                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;

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

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

    sol[1] = 1;

    dijkstra(1);

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

    return 0;
}