#include <bits/stdc++.h>

using namespace std;

class Edge
{
 private:
     int to;
     double cost;
     Edge(int to = 0, double cost = 0) :
         to(to), cost(cost) {};
   friend class Graph;
};

class Graph
{
private:
    vector<vector<Edge>>muchii;
    constexpr static int mod = 104659;
public:
    Graph() {};
    Graph(int N) {
        muchii.resize(N);
    }

    void add(int x, int y, double c) {
        muchii[x].push_back(Edge(y, c));
        muchii[y].push_back(Edge(x, c));
    }

    vector<int> compute() {
        const static int N = muchii.size();
        vector<double>Dp(N, 1e9);
        vector<int> how(N);
        vector<bool>vizitat(N);
        auto comp = [&] (const int &x, const int &y) {
            return Dp[x] > Dp[y];
        };
        priority_queue<int, vector<int>, decltype(comp)> Q (comp);
        Dp[0] = 0; how[0] = 1;
        Q.push(0);

        auto sunt_egale = [] (double x, double y) {
            return x - y < 1e-8;
        };
        auto e_bun = [] (double x, double y) {
            return x - y > 1e-8;
        };

        while(!Q.empty()) {
              int nod = Q.top();
              Q.pop();
              vizitat[nod] = false;

              for(auto tmp : muchii[nod]) {
                  int ce_dest = tmp.to;
                  double cost_nou = Dp[nod] + tmp.cost;
                  double &before_cost = Dp[ce_dest];
                  if(e_bun(before_cost, cost_nou)) {
                      before_cost = cost_nou;
                      how[ce_dest] = how[nod];

                      if(vizitat[ce_dest] == false) {
                         vizitat[ce_dest] = true;
                         Q.push(ce_dest);
                      }
                  }

                  else if(sunt_egale(cost_nou, before_cost)) {
                       how[ce_dest] += how[nod];
                       if(how[ce_dest] >= mod)
                          how[ce_dest] -= mod;
                  }
              }
        }
        return how;
    }
};

int n, m;
Graph G;

void read()
{
    ifstream cin("dmin.in");
    cin >> n >> m;
    G = Graph(n);
    while (m--) {
          int l, r, cc;
          cin >> l >> r >> cc;
          l--; r--;
          G.add(l, r, log(1.0 * cc));
    }
}

void solve() {
    ofstream cout("dmin.out");
    auto ans = G.compute();
    for(int i = 1; i < n; ++i)
        cout << ans[i] << ' ';
}

int main() {
    read();
    solve();
    return 0;
}