#include <fstream>
#include <vector>
#include <queue>
#define NMAX 1505
#define INF 1000000000000000
#define MOD 104659
#define pb push_back
#define ll long long
using namespace std;
ifstream fi("dmin.in");
ofstream fo("dmin.out");

ll n, m;
vector < pair <ll, ll> > G[NMAX];
ll d[NMAX], nr[NMAX];
priority_queue < pair <ll, ll> > Q;

void dijkstra()
{
    for (ll i = 2; i <= n; i++)
        d[i] = INF;

    d[1] = 0;
    nr[1] = 1;
    Q.push({0, 1});

    while (!Q.empty())
    {
        ll nod = Q.top().second;
        ll val = -Q.top().first;
        Q.pop();

        if (d[nod] != val)
            continue;

        for (auto v: G[nod])
        {
            if (d[nod] + v.second < d[v.first])
            {
                d[v.first] = d[nod] + v.second;
                nr[v.first] = 1;
                Q.push({-d[v.first], v.first});
            }
            else if (d[nod] + v.second == d[v.first])
            {
                nr[v.first]++;
                if (nr[v.first] >= MOD)
                    nr[v.first] -= MOD;
                Q.push({-d[v.first], v.first});
            }
        }
    }
}

int main()
{
    fi >> n >> m;
    for (ll i = 1; i <= m; i++)
    {
        ll u, v, c;
        fi >> u >> v >> c;
        G[u].pb({v, c});
        G[v].pb({u, c});
    }

    dijkstra();

    for (ll i = 2; i <= n; i++)
        fo << nr[i] << " ";

    return 0;
}