#include <bits/stdc++.h>

using namespace std;

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

const int MOD = 104659;
const long long INF = (1LL << 60);
const int DIM = 1500;

vector <pair<int, int>> v[DIM];
int n, m, x, y, c;

set <pair<int, int>> s;
long long dist[DIM];
int ways[DIM];
void dijkstra(int start){
    for(int i=1; i<=n; i++)
        dist[i]=INF;


    int nod, nxt, cst;

    dist[start] = ways[start] = 1;
    s.insert({dist[start], start});
    while(!s.empty()){
        nod = s.begin() -> second, s.erase(s.begin());

        for(int i = 0; i < v[nod].size(); i ++){
            nxt = v[nod][i].first;
            cst = v[nod][i].second;

            if(dist[nxt] > dist[nod] * cst){
                s.erase({dist[nxt], nxt});
                dist[nxt] = (long long)dist[nod] * cst;
                ways[nxt] = ways[nod];
                s.insert({dist[nxt], nxt});
            }else if(dist[nxt] == dist[nod] * cst)
                ways[nxt] = ((long long)ways[nxt] + ways[nod]) % MOD;
        }
    }
}

int main (){
    fin>>n>>m;
    while(m--){
        fin>>x>>y>>c;
        v[x].push_back({y, c});
        v[y].push_back({x, c});
    }
    dijkstra(1);

    for(int i = 2; i <= n; i ++)
        fout<<ways[i]<<" ";
    return 0;
}