#include <iostream>
#include <cmath>
#include <cstdio>
#include <queue>
#include <climits>
#include <vector>
using namespace std;
int n, m, i, j, sol[1501];
double dmin[1501];
vector<pair<int, double> > graph[1501];
struct comp{
    bool operator()(pair<int, double> x, pair<int, double> y){
        return dmin[x.first]>dmin[y.first];
    }
};
priority_queue<pair<int, double>, vector<pair<int, double> >, comp> q;
int main()
{
    freopen("dmin.in", "r", stdin);
    freopen("dmin.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(i=2; i<=n; ++i) dmin[i]=INT_MAX;
    for(i=1; i<=m; ++i){
        int x, y; double z;
        scanf("%d%d%lf", &x, &y, &z); z=log2(z);
        graph[x].push_back({y, z});
        graph[y].push_back({x, z});
    }
    sol[1]=1;
    for(q.push({1, 0}); !q.empty(); q.pop()){
        pair<int, double> node=q.top();
        for(auto i:graph[node.first]){
            if(dmin[i.first]!=INT_MAX && fabs(dmin[i.first]-dmin[node.first]+i.second)<0.0000001) {
                    sol[node.first]=(sol[i.first]+sol[node.first])%104659;
            }
            else if(dmin[i.first]==INT_MAX){
                dmin[i.first]=dmin[node.first]+i.second;
                q.push({i.first, dmin[i.first]});
            }
        }
    }
    for(i=2; i<=n; ++i) printf("%d ", sol[i]);
    return 0;
}