#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
#define ll double
#define inf 1e4
#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;
const double EPS = 1e-9;
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] = 0;
    nrDrumuri[1] = 1;
    priority_queue< pair<int,ll>, vector<pair<int,ll>>, alese> pq;
    pq.push({ 1,0});
    int nodCrt;
    ll costCrt;
    while (!pq.empty())
    {

        nodCrt = pq.top().first;
        costCrt = pq.top().second;
        pq.pop();
        if (abs(dist[nodCrt] - costCrt)<EPS) {
            for (auto i : graph[nodCrt]) {
                int nxtNod = i.first;
                ll newCost = costCrt + i.second;
                if (dist[nxtNod]- newCost>EPS) {
                    nrDrumuri[i.first] = nrDrumuri[nodCrt];
                    dist[i.first] = newCost;
                    pq.push(make_pair(nxtNod, dist[nxtNod]));
                }
                else if (abs(newCost - dist[nxtNod]) <= EPS) {
                    nrDrumuri[nxtNod]+=nrDrumuri[nodCrt];
                    nrDrumuri[nxtNod] %= MOD;
                }
            }
        }
    }
}
void read_input() {
    fin >> n >> m;
    graph.resize(n + 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;
        //logaritmam costul ca sa transform in inmultire
        //pt ca log(a*b)=log(a)+log(b)
        graph[u].push_back(make_pair(v, log2(cost)));
        graph[v].push_back(make_pair(u, log2(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;
}