#include <fstream>
#include <vector>
#include <queue>
#include <math.h>
#define int long long
#define double long double

using namespace std;

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

using pa = pair <int, double>;

const int MOD = 104659;

const double INF = 1e18;
const double Eps = 1e-6;

const int N = 1500;
int sol[N + 1];

double dp[N + 1];

int x, y, n, m;

double cost;

vector <pa> g[N + 1];

struct ceva
{
    double cost;
    int node;
    bool operator < (const ceva &a)const
    {
        return cost - a.cost < Eps;
    }
};
priority_queue <ceva> q;

inline double ab (double x)
{
    if (x < 0)return -x;
    return x;
}

void dijkstra (int node)
{
    for (int i = 1; i <= n; ++i)
        dp[i] = INF;
    dp[node] = 0;
    sol[node] = 1;
    q.push({0, node});
    while (!q.empty())
    {
        ceva x = q.top();
        q.pop();
        if (dp[x.node] < x.cost)
            continue;
        for (auto it : g[x.node])
        {
            double c = it.second;
            int y = it.first;
            if (dp[y] - (dp[x.node] + c) > Eps)
            {
                sol[y] = sol[x.node];
                dp[y] = dp[x.node] + c;
                q.push ({dp[y], y});
            }
            else if (ab(dp[y] - dp[x.node] - c) < Eps)
                sol[y] = (sol[y] + sol[x.node]) % MOD;
        }
    }
}

signed main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        cin >> x >> y >> cost;
        double real_cost = log(cost);
        g[x].push_back({y, real_cost});
        g[y].push_back({x, real_cost});
    }
    dijkstra (1);
    for (int i = 2; i <= n; ++i)
        cout << sol[i] << ' ';
    return 0;
}