#include <bits/stdc++.h>
#define pb push_back

using namespace std;

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

const int DIM = 1550;
const int MOD = 104659;

vector <pair<int, double>> v[DIM];

double c;
int n, m, x, y;

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

    int nod, nxt;
    double cst;

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

        for(int i=0; i < (int)v[nod].size(); i++){
            nxt = v[nod][i].first;
            cst = v[nod][i].second;
            if(dist[nod] + cst < dist[nxt]){
                s.erase({dist[nxt], nxt});
                dist[nxt] = dist[nod] + cst;
                ways[nxt] = ways[nod];
                s.insert({dist[nxt], nxt});
            }else if(dist[nod] + cst == dist[nxt])
                ways[nxt] += ways[nod], ways[nxt] %= MOD;
        }
    }

}

int main (){
    fin>>n>>m;
    while(m--){
        fin>>x>>y>>c;
        c = log(c);

        v[x].pb({y, c});
        v[y].pb({x, c});
    }

    dijkstra(1);

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