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

using namespace std;

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

const int MOD = 104659;
const int DIM = 1510;

double c;
int n, x, y;

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

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

    ways[start] = 1;
    s.insert({dist[start], start});

    int nod, nxt;
    double cst, dif;

    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;
            dif = dist[nxt] - dist[nod] - cst;

            if(-1e-9 < dif && dif < 1e-9)
                ways[nxt] += ways[nod], ways[nxt] %= MOD;
            else if(dist[nxt] > dist[nod] + cst){
                s.erase({dist[nxt], nxt});
                ways[nxt] = ways[nod];
                dist[nxt] = dist[nod] + cst;
                s.insert({dist[nxt], nxt});
            }
        }
    }
}

int main (){
    fin>>n;

    int edgeCnt; fin>>edgeCnt;
    while(edgeCnt--){
        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;
}
/**

**/