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

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

struct elem
{
    ll 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 (ll i = 2; i <= n; i++)
        d[i].first = 1e18;
    d[1].second = 1;
    q.push({1, 1, 0});
    while (!q.empty())
    {
        cout << q.top().nod << ' ' << q.top().cost << ' ' << q.top().nr << ' ' << d[q.top().nod].second << endl;
        if (!viz[q.top().nod])
        {
            viz[q.top().nod] = 1;
            for (pair<ll, ll> 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;
                }
        }
        q.pop();
    }
    for (ll i = 2; i <= n; i++)
        fcout << d[i].second << ' ';
    fcin.close();
    fcout.close();
    return 0;
}