#include <fstream>
#include <vector>
#include <queue>
#include <cmath>
#define int long long
using namespace std;

ifstream cin ("dmin.in");
ofstream cout ("dmin.out");

const double INF=1e18;
const int MOD=104659;

struct Edge {
    int to;
    double w;
};

int n,m;
vector<Edge> adj[1505];
double dist[1505];
int cnt[1505];

signed main() {
    cin>>n>>m;
    for (int i=1; i<=m; ++i) {
        int u, v;
        double cost;
        cin>>u>>v>>cost;
        double w=log(cost);
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    for (int i=1; i<=n; ++i) {
        dist[i]=INF;
    }
    dist[1]=0;
    cnt[1]=1;
    priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> pq;
    pq.push({0, 1});
    while (!pq.empty()) {
        auto [d, u]=pq.top();
        pq.pop();
        if (d>dist[u]+1e-9) continue;
        for (auto &edge:adj[u]) {
            int v=edge.to;
            double w=edge.w;
            if (dist[v]>dist[u]+w+1e-9) {
                dist[v]=dist[u]+w;
                cnt[v]=cnt[u];
                pq.push({dist[v], v});
            } else if (abs(dist[v]-(dist[u]+w))<=1e-9) {
                cnt[v]=(cnt[v]+cnt[u])%MOD;
            }
        }
    }
    for (int i=2; i<=n; ++i) {
        cout<<cnt[i]<<(i==n ? "" : " ");
    }
}