#include <iostream>
#include <fstream>
#include <utility>
#include <vector>
#include <queue>
#include <climits>
#include <cmath>

#define MOD 104659
#define EPS 0.000000001

using namespace std;

int N;
vector< vector< pair< int, double> > > G;
vector<long long> nrd;
vector<double> dmin;

int comp(double x, double y) {
    double abs = x - y;
    if(abs < 0)     abs = -abs;
    if(abs < EPS)
        return 0;
    return (x > y ? 1 : -1);
}
void Read();
void BellmanFord();
void Write();

int main()
{
    Read();
    BellmanFord();
    Write();

    return 0;
}

void BellmanFord() {
    queue<int> Q;
    vector<bool> inQueue;
    inQueue.assign(N + 1, 0);
    dmin[1] = 0;    nrd[1] = 1;
    Q.push(1);      inQueue[1] = 1;

    while(!Q.empty()) {
        int node = Q.front();   Q.pop();
        inQueue[node] = 0;

        for(int i = 0; i < G[node].size(); i++) {
            int neigh = G[node][i].first;
            double cost = G[node][i].second;
            if(comp(dmin[neigh], dmin[node] + cost  + EPS) > 0)   {
                dmin[neigh] = dmin[node] + cost;
                nrd[neigh] = nrd[node];
                if(!inQueue[neigh]) {
                    Q.push(neigh);
                    inQueue[neigh] = 1;
                }
            }
            else if(comp(dmin[neigh], dmin[node] + cost) == 0) {
                nrd[neigh] = (nrd[node] % MOD + nrd[neigh] % MOD ) % MOD;
                if(!inQueue[neigh]) {   inQueue[neigh] = 1; Q.push(neigh);  }
            }
        }
    }
}

void Write() {
    for(int i = 2; i <= N; i++)
        cout << nrd[i] % MOD << ' ';
    cout << '\n';
}
void Read() {
    freopen("dmin.in", "rt", stdin);
    freopen("dmin.out", "wt", stdout);
    int M;
    scanf("%d%d", &N, &M);
    G.assign(N + 2, vector<pair<int, double> >());
    while(M--) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        double logc = log(c);
        G[a].push_back(make_pair(b, logc));
        G[b].push_back(make_pair(a, logc));
    }
    dmin.assign(N + 2, INT_MAX);
    nrd.assign(N + 2, 0);
}