#include <iostream>
#include <queue>
#include <fstream>
#include <vector>
#include <cmath>
#define MOD 104659
#define MAX ((1<<30)-1)
#define epsilon 0.0000001
using namespace std;
ifstream f ("dmin.in");
ofstream g ("dmin.out");
int n,m;
vector<pair<int,double>>adiacenta[1501];
int fr[1501];
double costuri[1501];
priority_queue<pair<double,int>,vector<pair<double,int>>,greater<pair<double,int>>>q;
//doarece pentru a afla costul trebuie sa inmultim => la numere prea mari
//logaritmizand le putem doar aduna(prop log) si putem verifica daca sunt egale pentru calculalrea drumurilor posibile
void citire()
{
    f >> n >> m;
    for(int i = 1;i<=m;i++)
    {
        int x,y;
        double c;
        f >> x >> y >> c;
        c = log2(c);
        adiacenta[x].push_back({y,c});
        adiacenta[y].push_back({x,c});
    }
}
void init()
{
    for(int i = 1;i<=n;i++)
    {
        costuri[i] = MAX;
    }
}
void alg()
{
    costuri[1] = 0;
    fr[1] = 1;
    q.push({0,1});
    while(!q.empty())
    {
        int curent_nod = q.top().second;
        double curent_cost = q.top().first;
        q.pop();

        for(auto x:adiacenta[curent_nod])
        {
            int vecin_nod = x.first;
            double vecin_cost = x.second;
            if(costuri[vecin_nod] - (curent_cost+vecin_cost)>epsilon)
            {
                costuri[vecin_nod] = curent_cost+vecin_cost;
                fr[vecin_nod] = fr[curent_nod];
                q.push({costuri[vecin_nod],vecin_nod});
            }
            else
                if(abs(costuri[vecin_nod] - (curent_cost+vecin_cost))<epsilon)
                {
                    fr[vecin_nod] = (fr[vecin_nod]+fr[curent_nod])%MOD;
                }
        }
    }
}
int main()
{
    citire();
    init();
    alg();
    for(int i = 2;i<=n;i++)
        g << fr[i]<< " ";
}