#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define ll long long
#define inf 1e18
#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 a.second > b.second;
    }
};
void Disjaktra(int nodStart) {
    dist[1] = 1;//trebuie sa incepem de la 1 ,chiar daca raspunsul e 0 ca 1 e element neutru
    nrDrumuri[1] = 1;
    priority_queue< pair<int,ll>, vector<pair<int,ll>>, alese> pq;
    pq.push({ 1,1 });
    int nodCrt;
    ll 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]) {
                int nxtNod = i.first;
                int newCost = costCrt * i.second;
                if (newCost < dist[nxtNod]) {
                    nrDrumuri[i.first] = nrDrumuri[nodCrt];
                    dist[i.first] = newCost;
                    pq.push(make_pair(nxtNod, dist[nxtNod]));
                }
                else if (newCost == dist[nxtNod]) {
                    nrDrumuri[nxtNod]+=nrDrumuri[nodCrt];
                    nrDrumuri[nxtNod] %= MOD;
                }
            }
            lastVal[nodCrt] = costCrt;
        }
    }
}
void read_input() {
    fin >> n >> m;
    graph.resize(n + 1);
    lastVal.resize(n + 1, -1);
    nrDrumuri.resize(n + 1,0);
    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;
    }
  
}
void afis() {
    for (int i = 2; i <= n; ++i) {
        fout << nrDrumuri[i] << " ";
    }
}
int main()
{
    read_input();
    Disjaktra(1);
    afis();
    return 0;
}