#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 1500;
const int kMaxM = 2500;
const int kMod = 104659;
const long double kInf = numeric_limits <long double> :: max();
const long double kEps = (long double) 1e-12;
const int NIL = -1;

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

Edge l[2 * kMaxM];
int adj[kMaxN];

long double minCost[kMaxN];
int solutionCount[kMaxN];

queue <int> Q;
bool inQueue[kMaxN];

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

void bellmanFord(int N) {
  for (int i = 1; i < N; i++) {
    minCost[i] = kInf;
    inQueue[i] = 0;
    solutionCount[i] = 0;
  }

  Q.push(0);
  solutionCount[0] = 1;
  minCost[0] = .0;
  while (!Q.empty()) {
    int u = Q.front();
    Q.pop();
    inQueue[u] = 0;
    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];
        if (!inQueue[v]) {
          inQueue[v] = 1;
          Q.push(v);
        }
      } else if (fabs(minCost[v] - minCost[u] - l[i].cost) <= kEps) {
        solutionCount[v] = (solutionCount[v] + solutionCount[u]) % kMod;
        if (!inQueue[v]) {
          inQueue[v] = 1;
          Q.push(v);
        }
      }
    }
  }
}

int main(void) {
  ifstream in("dmin.in");
  ofstream out("dmin.out");
  in.tie(0);
  ios_base::sync_with_stdio(0);
  int N, M;
  int u, v;
  long double x;

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

  bellmanFord(N);

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