#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;

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

const int N = 1502;
const double eps = 0.0000001;
const int M = 104659;

int n, m, sol[N], nod;
double dist[N];
bool ver[N];
vector<pair<int, double> > v[N];
queue<int> q;

void dijkstra() {
    int i;
    vector<pair<int, double> >::iterator it;

    for(i = 1; i<=n; ++i)
        dist[i] = 29999999.0;

    ver[1] = true;
    q.push(1);
    dist[1] = 0;
    sol[1] = 1;

    while(!q.empty()) {
        nod = q.front();
        q.pop();
        ver[nod] = false;

        for(it = v[nod].begin(); it!=v[nod].end(); ++it) {
            if(dist[it->first] - dist[nod] - it->second > eps) {
                dist[it->first] = dist[nod] + it->second;
                sol[it->first] = sol[nod];

                if(!ver[it->first]) {
                    q.push(it->first);
                    ver[it->first] = true;
                }
            }
            else if(dist[nod] + it->second - dist[it->first] <= eps) {
                sol[it->first] += sol[nod];
                sol[it->first]%=M;
            }
        }
    }
}

int main() {
    int i, x, y;
    double c;

    in >> n >> m;

    for(i = 1; i<=m; ++i) {
        in >> x >> y >> c;
        c = log(c);

        v[x].push_back(pair<int, double>(y, c));
        v[y].push_back(pair<int, double>(x, c));
    }

    dijkstra();

    for(i = 2; i<=n; ++i)
        out << sol[i] << " ";

    return 0;
}