#include <bits/stdc++.h>
using namespace std;
double inf = 1e10 + 1, d[10005];
long long ct[10005], mod = 104659;
int n, m, k;
struct da
{
    int nod;
    double cost;
    bool operator <(const da &a) const
    {
        return a.cost < cost;
    }
};
vector<da> v[10005];
ifstream f("dmin.in");
ofstream g("dmin.out");
double eps = 0.0001;
void dijkstra(int k, double d[])
{
    for(int i = 1; i <= n; i ++)
        d[i] = inf;
    d[k] = 1;
    ct[k] = 1;
    priority_queue<da> q;
    q.push({k, 1});
    while(!q.empty())
    {
        long long nod = q.top().nod;
        double cost = q.top().cost;
        q.pop();
        if(d[nod] == cost)
        {
            for(int i = 0; i < v[nod].size(); i ++)
            {
                int dest = v[nod][i].nod;
                double c1 = v[nod][i].cost;
                if(abs(cost + log(c1) - d[dest]) < eps)
                    ct[dest] += ct[nod], ct[dest] %= mod;
                else if(d[dest] > cost + log(c1))
                    d[dest] = cost + log(c1), q.push({dest, d[dest]}), ct[dest] = ct[nod];

            }
        }
    }
}
int main()
{

    f >> n >> m;
    int a, b, c;
    for(int i = 1; i <= m; i ++)
    {
        int x, y, cost;
        f >> x >> y >> cost;
        v[x].push_back({y, cost});
        v[y].push_back({x, cost});
    }
    dijkstra(1, d);
    for(int i = 2; i <= n; i ++)
        g << ct[i] << " " ;
    return 0;
}