#include <bits/stdc++.h>

using namespace std;

ifstream fin("dmin.in");
ofstream fout("dmin.out");

const int nmax = 1505, mod = 104659;
const long long inf = (1LL << 60);
long long drum[nmax];
int n, m, dp[nmax], viz[nmax];
vector <pair <int, int> > G[nmax];

struct state{
    int nod;
    double cost;
    bool operator < (const state &s) const{
        return cost > s.cost;
    }
};

priority_queue <state> pq;
int main(){
    fin >> n >> m;
    for (int i = 1; i <= m; ++i){
        int x, y, z;
        fin >> x >> y >> z;
        G[x].push_back({y, z});
        G[y].push_back({x, z});
    }
    for (int i = 2; i <= n; ++i){
        drum[i] = inf;
    }
    pq.push({1, 1});
    drum[1] = 1;
    dp[1] = 1;
    while (!pq.empty()){
        state s = pq.top();
        pq.pop();
        if (viz[s.nod] == true){
            continue;
        }
        viz[s.nod] = true;
        for (auto it : G[s.nod]){
            long long newCost = 1LL * s.cost * it.second;
            if (newCost < drum[it.first]){
                drum[it.first] = newCost;
                dp[it.first] = dp[s.nod];
                pq.push({it.first, newCost});
            }
            else if (newCost == drum[it.first]){
                dp[it.first] += dp[s.nod];
                if (dp[it.first] >= mod) dp[it.first] -= mod;
            }
        }
    }
    for (int i = 2; i <= n; ++i){
        fout << dp[i] << " ";
    }
    fin.close();
    fout.close();
    return 0;
}