#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
using namespace std;
const int Nmax = 1501;
const double eps = 0.0000001;
const int modulo = 104659;
vector <int> numar(Nmax);
vector <double> dist(Nmax);
bitset <Nmax> viz;
vector< pair<int,double> > Graf[Nmax];
queue <int> Q;
int N, M;
void citire(){
    ifstream f("dmin.in");
    f >> N >> M;
    int a, b;
    double c;
    for(; M; M--) {
        f >> a >> b >> c;
        c = log(c);
        Graf[a].push_back(pair<int, double>(b, c));
        Graf[b].push_back(pair<int, double>(a, c));
    }
}

void dijkstra() {
    vector< pair<int, double> >::iterator it;
    for(int i = 1; i <= N; ++i)
        dist[i] = 9999999.0;
    Q.push(1);
    dist[1] = 0;
    numar[1] = 1;
    viz[1] = 1;
    while(!Q.empty()){
        int nod = Q.front();
        Q.pop();
        for(it = Graf[nod].begin(); it != Graf[nod].end(); ++it){
            if(dist[it->first] - dist[nod] - it->second > eps){
                dist[it->first] = dist[nod] + it->second;
                numar[it->first] = numar[nod];
                if(!viz[it->first]){
                    viz[it->first] = 1;
                    Q.push(it->first);
                }
            }
            else
                if(dist[nod] + it->second - dist[it->first] <= eps){
                    numar[it->first] += numar[nod];
                    numar[it->first] %= modulo;
            }
        }
    }
}
void afis(){
    ofstream g("dmin.out");
    for(int i = 2; i <= N; ++i)
        g << numar[i] << " ";
}
int main() {
    citire();
    dijkstra();
    afis();
    return 0;
}