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

using ld = long double;

priority_queue<pair<ld, int>, vector<pair<ld, int>>, greater<pair<ld, int>>> pq;
ld min_dist[1510] = {};
int nr[1520] = {};
vector<pair<int, int>> vec[1510];

bool eq(ld a, ld b){
    return abs(a-b) < 1e-6; }

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

    int n, m;
    f >> n >> m;

    for(int i = 1; i <= n; ++i) min_dist[i] = numeric_limits<ld>::infinity();
    min_dist[1] = 1;
    nr[1] = 1;
    pq.emplace(1, 1);

    for(int i = 0; i < m; ++i){
        int x, y, z;
        f >> x >> y >> z;

        vec[x].emplace_back(y, z);
        vec[y].emplace_back(x, z); }
    
    while(!pq.empty()){
        ld x;
        int y;
        tie(x, y) = pq.top();
        pq.pop();
        if(!eq(x, min_dist[y])) continue;
        for(auto p : vec[y]){
            int cost;
            int which;
            tie(which, cost) = p;

            if(eq(min_dist[which], x * cost)){
                nr[which] += nr[y];
                nr[which] %= 104659; }
            else if(min_dist[which] > x * cost){
                min_dist[which] = x * cost;
                nr[which] = nr[y];
                pq.emplace(min_dist[which], which); } } }

    for(int i = 2; i <= n; ++i) g << nr[i] << ' ' ;
    return 0; }