#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <queue>
#include <limits>
#define err 0.000001
#define mod 104659
#define maxi 2000
#define INF numeric_limits<long double>::max()
using namespace std;
ifstream f;
ofstream g;
vector<pair<int,int>> V[maxi];
priority_queue<pair<long double,int>,vector<pair<long double,int>>,greater<pair<long double,int>>> heap;
queue<int> coada;
int n,m,a,b,c,dp[maxi];
long double D[maxi];
bool viz[maxi];
void READ()
{
    f.open("dmin.in",ios::in);
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>a>>b>>c;
        V[a].push_back(make_pair(b,c));
        V[b].push_back(make_pair(a,c));
    }
    f.close();
    return;
}
void INIT()
{
    for(int i=2;i<=n;i++)
        D[i]=INF;
}
void DIJKSTRA()
{
    INIT();
    heap.push(make_pair(D[1],1));
    while(!heap.empty())
    {
        int sursa=heap.top().second;
        if(!viz[sursa])
        {
            viz[sursa]=true;
            coada.push(sursa);
        }
        heap.pop();
        for(auto a:V[sursa])
        {
            int vecin=a.first;
            int cost=a.second;
            if(!viz[vecin])
            {
                if(D[sursa]+log2(cost)<D[vecin])
                {
                    D[vecin]=D[sursa]+log2(cost);
                    heap.push(make_pair(D[vecin],vecin));
                }
            }
        }
    }
}
int main()
{
    g.open("dmin.out",ios::out);
    READ();
    DIJKSTRA();
    dp[1]=1;
    while(!coada.empty())
    {
        int sursa=coada.front();
        for(auto a:V[sursa])
        {
            int vecin=a.first;
            int cost=a.second;
            if(abs(D[sursa]-(D[vecin]+log2(cost)))<=err)
                dp[sursa]=(dp[sursa]+dp[vecin])%mod;
        }
        coada.pop();
    }
    for(int i=2;i<=n;i++)
        g<<dp[i]<<" ";
    g.close();
    return 0;
}