#include <bits/stdc++.h>
using namespace std;
ifstream fin("dmin.in");
ofstream fout("dmin.out");
const int NMAX=1501, MOD=104659;
const long double epsilon=1e-9;
int n, m;
int nr[NMAX];
long double d[NMAX];
vector<pair<int, long double>> g[NMAX];
priority_queue<pair<long double,int>, vector<pair<long double,int>>, greater<pair<long double,int>>> pq;
bitset<NMAX> viz;

bool egal(long double a, long double b){
    return fabsl(a-b) < epsilon;
}

int main(){
    fin>>n>>m;
    int x, y;
    long double w;
    for(int i=1;i<=m;i++){
        fin>>x>>y>>w;
        long double lw = log2l(w);
        g[x].push_back({y, lw});
        g[y].push_back({x, lw});
    }

    d[1]=0;
    nr[1]=1;
    pq.push({0, 1});
    for(int i=2;i<=n;i++)
        d[i]=1e18;

    while(!pq.empty()){
        int nod=pq.top().second;
        pq.pop();

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

        for(auto vec : g[nod]){
            long double nd = d[nod] + vec.second;
            if(egal(d[vec.first], nd)){
                nr[vec.first]=(nr[vec.first]+nr[nod])%MOD;
            }
            else if(d[vec.first] > nd){
                d[vec.first] = nd;
                nr[vec.first] = nr[nod];
                pq.push({d[vec.first], vec.first});
            }
        }
    }

    for(int i=2;i<=n;i++){
        fout<<nr[i]<<' ';
    }
    return 0;
}