#include <bits/stdc++.h>

using namespace std;

ifstream f("dmin.in");
ofstream g("dmin.out");

const int NMAX = 1505;
const int mod = 104659;
const long double inf = LDBL_MAX / 2;
int n,m,viz[NMAX],ans[NMAX];
long double dist[NMAX];
vector < pair < int, long double > > v[NMAX];
priority_queue < pair < long double, int > > q;

int main(){
    int i,x,y,node;
    long long z,cost,value;
    f >> n >> m;
    for(i = 1 ; i <= m ; i++){
        f >> x >> y >> z;
        z = log2(z);
        v[x].push_back(make_pair(y,z));
        v[y].push_back(make_pair(x,z));
    }

    for(i = 2 ; i <= n ; i++)
        dist[i] = inf;
    ans[1] = 1;

    q.push(make_pair(0, 1));
    while(!q.empty()){
        node = q.top().second;
        cost = -q.top().first;
        q.pop();

        if(viz[node])
            continue;
        viz[node] = 1;

        for(auto it: v[node]){
            value = dist[node] + it.second;
            if(dist[it.first] > value){
                dist[it.first] = value;
                ans[it.first] = ans[node];
                q.push(make_pair(-value, it.first));
            }else
                if(dist[it.first] == value){
                    ans[it.first] = (ans[it.first] + ans[node]) % mod;
                }
        }
    }


    for(i = 2 ; i <= n ; i++)
        g << ans[i] << " ";

    return 0;
}