#include <bits/stdc++.h>

#define inf 1LL<<61;
#define MOD 104659
#define f first
#define s second

using namespace std;

ifstream F("dmin.in");
ofstream G("dmin.out");

int n, m, x, y, c;
long long d[1505], k[1505];
vector<pair<int, int> > a[1505];
priority_queue<pair<long long, int> > pq;
bitset<1505> w;

int main()
{
    F >> n >> m;
    for(int i = 0; i < m; ++ i)
    {
        F >> x >> y >> c;
        a[x].push_back({y, c});
        a[y].push_back({x, c});
    }
    for(int i = 2;i <= n; ++ i) d[i] = inf;
    pq.push({1, 1}); d[1] = 1; k[1]=1;
    vector<pair<int, int> > :: iterator it;
    while(!pq.empty())
    {
        x = pq.top().s;
        pq.pop();
        if(w[x]) continue;
        w[x] = 1;
        for(it = a[x].begin(); it != a[x].end(); ++ it)
            if(d[(*it).f] > 1LL*(*it).s * d[x])
                d[(*it).f] = 1LL*(*it).s * d[x], k[(*it).f] = k[x], pq.push({-d[(*it).f], (*it).f});
            else if(d[(*it).f] == 1LL*(*it).s * d[x])
                k[(*it).f] = (k[(*it).f] + k[x])%MOD;
    }
    for(int i = 2;i <= n; ++ i) G << k[i] << " ";
    return 0;
}