#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define ll long long
#define inf 1e8
#define MOD 104659
using namespace std;
ifstream fin("dmin.in");
ofstream fout("dmin.out");
vector<vector<pair<int,int>>>graph;
int n, m;

vector<ll>dist;
vector<ll>lastVal;//trebuie un vector de (kind of) de visited ca sa nu trecem printr-un nod de 2 ori
//verifica sa nu trecem de 2 ori printr-un nod pt ca poate avea o alta valoare de 2 ori
vector<int>nrDrumuri;
struct alese {
    bool operator ()(pair<int, ll> a, pair<int, ll> b) {
        return dist[a.first] > dist[b.first];
    }
};
void Disjaktra(int nodStart) {
    nrDrumuri[1] = 1;
    priority_queue< pair<int,ll>, vector<pair<int,ll>>, alese> pq;
    pq.push({ 1,1 });
    int nodCrt, costCrt;
    while (!pq.empty())
    {

        nodCrt = pq.top().first;
        costCrt = pq.top().second;
        pq.pop();
        if (dist[nodCrt] == costCrt && lastVal[nodCrt]!=costCrt) {

            for (auto i : graph[nodCrt]) {
                if (costCrt * i.second < dist[i.first]) {
                    nrDrumuri[i.first] = nrDrumuri[nodCrt];
                    dist[i.first] = costCrt * i.second;
                    pq.push(make_pair(i.first, dist[i.first]));
                }
                else if (costCrt * i.second == dist[i.first]) {
                    nrDrumuri[i.first]+=nrDrumuri[nodCrt];
                    nrDrumuri[i.first] %= MOD;
                    pq.push(make_pair(i.first, dist[i.first]));
                }
            }
            lastVal[nodCrt] = costCrt;
        }
    }
}
void read_input() {
    fin >> n >> m;
    graph.resize(n + 1);
    lastVal.resize(n + 1, -1);
    nrDrumuri.resize(n + 1);
    dist.resize(n + 1);//dist[j]=distanta minima de la nodul 1 la nodul j
    int cost,u,v;
    for (int i = 0; i < m; ++i) {
        fin >> u >> v >> cost;
        graph[u].push_back(make_pair(v, cost));
        graph[v].push_back(make_pair(u, cost));
    }
    for (int i = 0; i < dist.size(); ++i) {
        dist[i] = inf;
    }
    dist[1] = 1;//trebuie sa incepem de la 1 ,chiar daca raspunsul e 0 ca 1 e element neutru
}
void afis() {
    for (int i = 2; i <= n; ++i) {
        fout << nrDrumuri[i] << " ";
    }
}
int main()
{
    read_input();
    Disjaktra(1);
    afis();
    return 0;
}