#include <bits/stdc++.h>

using namespace std;
ifstream in("dmin.in");
ofstream out("dmin.out");
const int N = 1505;
const double EPS = 1e-10;
const int MOD = 104659;
typedef long double ld;
vector< pair<int,ld> >v[N];
int dp[N];
ld dist[N];
bool eq(ld x, ld y)
{
    return (abs(x-y)<EPS);
}
int main()
{
    int n,m;
    in >> n >> m;
    for (int i = 1; i<=m; i++)
    {
        int x,y;
        ld c;
        in >> x >> y >> c;
        c = log2(c);
        v[x].push_back({y,c});
        v[y].push_back({x,c});
    }
    priority_queue< pair<ld, int> > q;
    q.push({0,1});
    for (int i = 2; i<=n; i++)
        dist[i] = 1e9;
    dp[1] = 1;
    while (!q.empty())
    {
        int now = q.top().second;
        q.pop();
        for (auto it: v[now])
        {
            int next = it.first;
            ld cost = it.second;
            if (dist[next]-(dist[now]+cost)>EPS)
            {
                dist[next] = dist[now]+cost;
                dp[next] = dp[now];
                q.push({-dist[next],next});
            }
            else if (eq(dist[next],dist[now]+cost))
            {
                dp[next]+=dp[now];
            }
            if (dp[next]>MOD)
                dp[next]-=MOD;
        }
    }
    for (int i = 2; i<=n; i++)
        out << dp[i] << " ";
}