#include <cmath>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

struct Nod
{
 double cost = (1 << 30);
 vector<pair<int, double>> vecini;
};

typedef vector<Nod> Graf;
typedef pair<int, double> Pereche;

const int kMod = 104659;
const double kEpsilon = 0.00001;

inline double Log2(int n)
{
 return log(n) / log(2);
}

void AflaDistante(Graf &g)
{
 auto cmp = [](const Pereche &a, const Pereche &b) -> bool { return a.second > b.second; };
 priority_queue<Pereche, vector<Pereche>, decltype(cmp)> coada(cmp);

 g[1].cost = 0;
 coada.push({ 1, 0 });

 while (!coada.empty()) {
  int nod = coada.top().first;
  double cost = coada.top().second;
  coada.pop();

  if (cost != g[nod].cost) continue;

  for (auto &muchie : g[nod].vecini) {
   int vecin = muchie.first;
   double cost_nou = cost + muchie.second;
   if (g[vecin].cost - cost_nou > kEpsilon) {
    g[vecin].cost = cost_nou;
    coada.push({ vecin, cost_nou });
   }
  }
 }
}

vector<int> AflaModuri(const Graf &g)
{
 vector<int> moduri(g.size(), 0);
 queue<int> coada;
 vector<bool> in_coada(g.size(), false);

 coada.push(1);
 moduri[1] = 1;
 in_coada[1] = true;

 while (!coada.empty()) {
  int nod = coada.front();
  coada.pop();

  for (auto &muchie : g[nod].vecini) {
   int vecin = muchie.first;
   if (abs(g[vecin].cost - g[nod].cost - muchie.second) <= kEpsilon && g[vecin].cost - g[nod].cost > kEpsilon) {
    moduri[vecin] += moduri[nod];
    moduri[vecin] %= kMod;
    if (!in_coada[vecin]) {
     coada.push(vecin);
     in_coada[vecin] = true;
    }
   }
  }
 }
 return moduri;
}

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

 int n, m;
 fin >> n >> m;

 Graf graf(n + 1);
 while (m--) {
  int x, y, c;
  fin >> x >> y >> c;

  double cost = Log2(c);
  graf[x].vecini.push_back({ y, cost });
  graf[y].vecini.push_back({ x, cost });
 }

 AflaDistante(graf);

 auto raspuns = AflaModuri(graf);
 for (int i = 2; i < raspuns.size(); ++i)
  fout << raspuns[i] << " ";

 return 0;
}