#include <iostream>
#include <bits/stdc++.h>
#define Nmax 1503
#define mod 104659

using namespace std;

ifstream f ("dmin.in");
ofstream g ("dmin.out");

int n,m,i,x,y,c,d[Nmax], nrDrum[Nmax],nod,next_nod,l,cost,INF = 0x3f3f3f3f;
vector < pair < int,int > > v[Nmax];
set < pair < int,int > > heap;

int main()
{
    f >> n >> m;
    for(i = 1;i <= m;i++)
    {
        f >> x >> y >> c;
        v[x].push_back({y,c});
        v[y].push_back({x,c});
    }

    memset(d , INF , sizeof(d));
    heap.insert({0,1});
    d[1] = 0;
    nrDrum[1] = 1;

    while(not heap.empty())
    {
        nod = heap.begin() -> second;
        c = heap.begin() -> first;
        heap.erase(heap.begin());
        l = v[nod].size();
        for(i = 0;i < l;i++)
        {
            next_nod = v[nod][i].first;
            cost = v[nod][i].second;
            if(d[next_nod] > d[nod] + cost)
            {
                if(d[next_nod] != INF)
                heap.erase(heap.find({d[next_nod],next_nod}));

                d[next_nod] = d[nod] + cost;
                heap.insert({d[next_nod],next_nod});
                nrDrum[next_nod] = nrDrum[nod];
            }
            else if(d[next_nod] == d[nod] + cost)
                nrDrum[next_nod] = (nrDrum[nod] + nrDrum[next_nod]) % mod;
        }
    }

    for(i = 2;i <= n;i++)
        g << nrDrum[i] << " ";
    return 0;
}