#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define MOD 104659
using namespace std;
ifstream in("dmin.in");
ofstream out("dmin.out");
const int NR = 1505 ;
const int oo = ( 1 << 30 ) ;
vector < pair < int , int > > v[ NR ] ;
vector < int64_t > d ( NR , oo ) ;
int n , m , ans [ NR ] ;
void bellman ( int start )
{
    queue < int > q ;
    q.push( start ) ;
    d [ start ] = 1 ;
    ans [ start ] = 1 ;
    while ( !q.empty() )
    {
        int nod = q.front() ;
        q.pop() ;
        for ( size_t i = 0 ; i < v [ nod ].size() ; ++ i )
        {
            if ( d [ nod ] * v [ nod ][ i ].s == d [ v [ nod ][ i ].f ] ) ans [ v [ nod ][ i ].f ] += ans [ nod ] , ans [ v [ nod ][ i ].f ] %= MOD ;
            if ( d [ nod ] * v [ nod ][ i ].s <  d [ v [ nod ][ i ].f ] ) ans [ v [ nod ][ i ].f ] = ans [ nod ] , q.push ( v [ nod ][ i ].f ) , d [ v [ nod ][ i ].f ] = d [ nod ] * v [ nod ][ i ].s , ans [ v [ nod ][ i ].f ] %= MOD ; ;
        }
    }
}
int main()
{
    in >> n >>  m ;
    while ( m -- )
    {
        int x , y , z ;
        in >> x >> y >> z ;
        v [ x ].pb( mp ( y , z ) ) ;
        v [ y ].pb( mp ( x , z ) ) ;
    }
    bellman( 1 ) ;
    for ( int i = 2 ; i <= n ; ++ i )   out << ans [ i ] << ' ' ;
}