#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ifstream fcin("dmin.in");
ofstream fcout("dmin.out");

const int N = 1505;
const int mod = 104659;
int n, m, a, b, c;
vector<pair<int, int>> v[N];
bool viz[N];
pair<ll, int> d[N]; /// cost, number of ways

struct elem
{
    int nod, nr;
    ll cost;
    bool operator <(const elem &x) const
    {
        return cost > x.cost;
    }
};
priority_queue<elem> q;

int main()
{
    fcin >> n >> m;
    while (m--)
    {
        fcin >> a >> b >> c;
        v[a].push_back({b, c});
        v[b].push_back({a, c});
    }
    for (int i = 2; i <= n; i++)
        d[i].first = 1e18;
    d[1].second = 1;
    q.push({1, 1, 0});
    while (!q.empty())
    {
        if (!viz[q.top().nod])
        {
            viz[q.top().nod] = 1;
            for (pair<int, int> e : v[q.top().nod])
                {
                    if (d[q.top().nod].first + e.second < d[e.first].first)
                    {
                        d[e.first].first = d[q.top().nod].first + e.second;
                        d[e.first].second = d[q.top().nod].second;
                        q.push({e.first, d[e.first].second, d[e.first].first});
                    }
                    else if (d[q.top().nod].first + e.second == d[e.first].first)
                        d[e.first].second = (d[e.first].second + d[q.top().nod].second) % mod;
                }
        }
        else if (d[q.top().nod].first == q.top().cost)
            d[q.top().nod].second = (d[q.top().nod].second + q.top().nr) % mod;
        q.pop();
    }
    for (int i = 2; i <= n; i++)
        fcout << d[i].second << ' ';
    fcin.close();
    fcout.close();
    return 0;
}