#include <bits/stdc++.h>
#define x first
#define y second
#define eps 1e-9
#define mod 104659
using namespace std;
ofstream fout ("dmin.out");
ifstream fin ("dmin.in");
queue < int > q;
priority_queue < pair < long double , int > > pq;
vector < pair < int , long double > > w[2000];
vector < pair < long double , int > > costuri;
int viz[2000],n,m,a,b,aux1,crt,i,dp[2000];
long double c,rsp[2000];
pair < long double , int > aux;
int main()
{
    fin>>n>>m;
    for( i = 1 ; i <= m ; i++ )
    {
        fin>>a>>b>>c;
        c = log( c );
        w[ a ].push_back( { b , c } );
        w[ b ].push_back( { a , c } );
    }
    pq.push( { 0.0 , 1 } );
    while( pq.size() )
    {
        aux = pq.top();
        pq.pop();
        if( viz[ aux.y ] == 1 )
            continue;
        viz[ aux.y ] = 1;
        rsp[ aux.y ] = -aux.x;
        for( auto it : w[ aux.y ] )
            if( !viz[ it.x ] )
                pq.push( { aux.x - it.y , it.x } );
    }
    for( i = 1 ; i <= n ; i++ )
        costuri.push_back( { rsp[ i ] , i } );
    sort( costuri.begin() , costuri.end() );
    dp[ 1 ] = 1;
    for( auto it : costuri )
    {
        for( auto it2 : w[ it.y ] )
        {
            if( abs( rsp[ it2.x ] - rsp[ it.y ] - it2.y ) <= eps )
                dp[ it2.x ] = ( dp[ it2.x ] + dp[ it.y ] ) % mod;
        }
    }
    for( i = 2 ; i <= n ; i++ )
        fout<<dp[ i ]<<" ";
}