#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cmath>
#define EPS 0.0000001
#define MOD 104659
using namespace std;
ifstream f ("dmin.in");
ofstream g ("dmin.out");
vector<pair<int,double>>adiacenta[1501];
double distante[1501];
int fr[1501];
priority_queue<pair<double,int>, vector<pair<double,int>>, greater<pair<double,int>>>q;
int n,m;
void citire()
{
    f >> n >> m;
    for(int i = 1;i<=m;i++)
    {
        int x,y,c;
        f >> x >> y >> c;
        double rasp = log2(c);
        adiacenta[x].push_back({y,rasp});
        adiacenta[y].push_back({x,rasp});
    }
}
void init()
{
    for(int i = 1;i<=n;i++)
    {
        distante[i] = (1<<30)-1;
    }
}
void djkastra()
{
    q.push({0,1});
    fr[1] = 1;
    distante[1] = 0;
    while(!q.empty())
    {
        int nod_curent = q.top().second;
        double cost_curent = q.top().first;
        q.pop();
        for(auto x:adiacenta[nod_curent])
        {
            int vecin_nod = x.first;
            double vecin_cost = x.second;
            if(distante[vecin_nod]-(cost_curent+vecin_cost)>EPS)
            {
                distante[vecin_nod]=cost_curent+vecin_cost;
                fr[vecin_nod] = fr[nod_curent];
                q.push({distante[vecin_nod],vecin_nod});
            }
            else if(abs(distante[vecin_nod]-(cost_curent+vecin_cost))<EPS)
            {
                fr[vecin_nod] =(fr[vecin_nod]+fr[nod_curent])%MOD;
            }
        }
    }

}
int main()
{
    citire();
    init();
    djkastra();
    for(int i = 2;i<=n;i++)
        g << fr[i]<< " ";
}