#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <math.h>

#define INF 0x3f3f3f3f
#define maxn 1505


using namespace std;

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

const int Const = 104659;
const double eps = 1e-8;

inline int Modulus (int number){
    return number % Const;
}

inline int abs (double number){
    return number < 0 ? -number : number;
}

vector < pair<int, double> > v[maxn];
priority_queue < pair <int, double>, vector < pair <int, double> >, greater < pair <int, double> > > pq;

int n, m;
double dist[maxn];
int sptSet[maxn], sol[maxn];

void dijkstra(){

    for(int i = 2; i <= n; ++i) dist[i] = INF;

    pq.push(make_pair(1,0));
    sol[1] = 1;
    dist[1] = 0;

    while(!pq.empty()){

        int u = pq.top().first;
        pq.pop();

        for(int i = 0; i < v[u].size(); ++i){
            int nod = v[u][i].first;
            double distance = v[u][i].second;
            if(dist[u] + distance + eps < dist[nod]){
                dist[nod] = dist[u] + distance;
                sol[nod] = sol[u];
                pq.push(make_pair(nod, dist[nod]));

            }
            else if (abs(dist[nod] - dist[u] - distance) <= eps){
                sol[nod] = Modulus(sol[nod] + sol[u]);
            }
        }
    }
}

int main (){
    f >> n >> m;
    for (int i = 1; i <= m; ++i){
        int x, y, d;
        f >> x >> y >> d;
        v[x].push_back(make_pair(y,log(d)));
        v[y].push_back(make_pair(x,log(d)));
    }

    dijkstra();
    for(int i = 2; i <= n; ++i) g << sol[i] << ' ';
}