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

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

const int N = 1502;
const double eps = 0.0000001;
const int M = 104659;

int n, m, sol[N], nod;
double dist[N];
bool ver[N];
vector<pair<int, double> > v[N];
queue<int> q;

void dijkstra() {
 int i;
 vector<pair<int, double> >::iterator it;

 for(i = 1; i<=n; ++i)
  dist[i] = 29999999.0;

 ver[1] = true;
 q.push(1);
 dist[1] = 0;
 sol[1] = 1;

 while(!q.empty()) {
  nod = q.front();
  q.pop();
  ver[nod] = false;

  for(it = v[nod].begin(); it!=v[nod].end(); ++it) {
   if(dist[it->first] - dist[nod] - it->second > eps) {
    dist[it->first] = dist[nod] + it->second;
    sol[it->first] = sol[nod];

    if(!ver[it->first]) {
     q.push(it->first);
     ver[it->first] = true;
    }
   }
   else if(dist[nod] + it->second - dist[it->first] <= eps) {
    sol[it->first] += sol[nod];
    sol[it->first]%=M;
   }
  }
 }
}

int main() {
 int i, x, y;
 double c;

 in >> n >> m;

 for(i = 1; i<=m; ++i) {
  in >> x >> y >> c;
  c = log(c);

  v[x].push_back(pair<int, double>(y, c));
  v[y].push_back(pair<int, double>(x, c));
 }

 dijkstra();

 for(i = 2; i<=n; ++i)
  out << sol[i] << " ";

 return 0;
}