#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 1500;
const int kMaxM = 2500;
const double kEps = 1e-12;
const double kInf = 1000.00;
const int kMod = 104659;
const int NIL = -1;

struct Edge {
  int v, next;
  double cost;
};

Edge l[2 * kMaxM];
int adj[kMaxN];
double minCost[kMaxN];
int solutionCount[kMaxN];

struct costCmp {
  bool operator () (const int &A, const int &B) {
    return minCost[A] > minCost[B];
  }
};

priority_queue <int, vector <int>, costCmp> Q;

void addEdge(const int &u, const int &v, const double &cost, const int &pos) {
  l[pos].v = v;
  l[pos].cost = cost;
  l[pos].next = adj[u];
  adj[u] = pos;
}

int main(void) {
  ifstream in("dmin.in");
  ofstream out("dmin.out");
  int N, M;

  in >> N >> M;
  for (int i = 0; i < N; i++) {
    adj[i] = NIL;
  }
  for (int i = 0; i < M; i++) {
    int u, v, x;
    in >> u >> v >> x;
    double cost = log(static_cast <double> (x));
    addEdge(u - 1, v - 1, cost, 2 * i);
    addEdge(v - 1, u - 1, cost, 2 * i + 1);
  }
  in.close();

  for (int i = 1; i < N; i++) {
    minCost[i] = kInf;
  }
  Q.push(0);
  solutionCount[0] = 1;
  do {
    int u = Q.top();
    Q.pop();
    for (int i = adj[u]; i != NIL; i = l[i].next) {
      int v = l[i].v;
      if (minCost[v] - minCost[u] - l[i].cost > kEps) {
        minCost[v] = minCost[u] + l[i].cost;
        solutionCount[v] = solutionCount[u];
        Q.push(v);
      } else if (fabs(minCost[v] - minCost[u] - l[i].cost) <= kEps) {
        solutionCount[v] += solutionCount[u];
        solutionCount[v] %= kMod;
      }
    }
  } while (!Q.empty());

  for (int i = 1; i < N; i++) {
    out << solutionCount[i] << " \n"[i == N - 1];
  }
  out.close();
  return 0;
}