#include <fstream>
#include <vector>
#include <queue>
#include <climits>
#include <cmath>
using namespace std;
ifstream cin("dmin.in");
ofstream cout("dmin.out");
const double INF = 1e18;
vector<double> 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<double,int>>> pq;
pq.push({0.0, 1});
while (!pq.empty()) {
auto [dist_curr, u] = pq.top();
pq.pop();
if (dist_curr > dist[u] + 1e-9) continue;
for (auto [x, y] : adj[u]) {
double 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] % 104659;
pq.push({dist[x], x});
}else if (abs(dist_nou - dist[x]) <= 1e-9) {
drumuri[x] = (drumuri[x] + drumuri[u]) % 104659;
}
}
}
}
int main() {
cin >> n >> m;
dist.resize(n + 1, INF); // 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++)
if (dist[i] == INF)
cout << 0 << " ";
else cout << drumuri[i] << " ";
return 0;
}