#include <fstream>
#include <vector>
#include <queue>
#include <climits>
#include <cmath>
using namespace std;
ifstream cin("dmin.in");
ofstream cout("dmin.out");
vector<long long> dist; // dist[i] = dist. minima de la nodul 1 la nodul i
vector<int> drumuri; // nr de drumuri min
vector<vector<pair<int,long long>>> adj;
int n, m;
void dijkstra() {
// tinem minte suma logaritmilor pt a evita overflow, -> log(a * b) = log(a) + log(b)
// min heap in care tinem perechi de tipul {suma_logaritmilor, nod}
priority_queue<pair<double,int>, vector<pair<double,int>>, greater<pair<int,int>>> pq;
pq.push({0.0, 1});
while (!pq.empty()) {
auto [dist_curr, u] = pq.top();
pq.pop();
if (dist_curr > dist[u]) continue;
for (auto [x, y] : adj[u]) {
long long dist_nou = dist_curr + log(y);
// daca am gasit un drum mai scurt, resetam nr in dist
if (dist_nou < dist[x]) {
dist[x] = dist_nou;
drumuri[x] = drumuri[u];
pq.push({dist[x], x});
}else if (dist_nou == dist[x]) {
drumuri[x] += drumuri[u];
}
}
}
}
int main() {
cin >> n >> m;
dist.resize(n + 1, INT_MAX); // initiam cu -1
drumuri.resize(n + 1, 0);
adj.resize(n + 1);
dist[1] = 0.0;
drumuri[1] = 1;
for (int i = 1; i <= m; i++) {
int c1, c2;
long long cost;
cin >> c1 >> c2 >> cost;
adj[c1].push_back({c2, cost});
adj[c2].push_back({c1, cost});
}
dijkstra();
for (int i = 2; i <= n; i++)
cout << drumuri[i] % 104659 << " ";
return 0;
}