#include <bits/stdc++.h>
#define MOD 104659
#define pb push_back
#define mp make_pair
#define f first
#define s second
using namespace std ;
const int NR = 1505 ;
const long double oo = 100000 ;
const double ER = 0.000000001;
ifstream in ("dmin.in") ;
ofstream out ("dmin.out") ;
vector < pair < int , long double > > v [ NR ] ;
vector < int > way ( NR , 0 ) ;
vector < long double > d ( NR , oo ) ;
int n , m ;
struct cmp {
    inline bool operator() ( const pair < int , long double > i , const pair < int , long double > j )  {
        return i.s > j.s ;
    }
};
priority_queue < pair < int , long double > , vector < pair < int , long double > > , cmp > q ;
void dijkstra ( )   {
    int nod ;
    long double cost ;
    q.push( mp ( 1 , 0 ) ) ;
    d [ 1 ] = 0 ;
    way [ 1 ] = 1 ;
    vector < pair < int , long double > > :: iterator it ;
    while ( !q.empty() )    {
            nod = q.top().f;
            cost = q.top().s ;
            q.pop() ;
        if ( d [ nod ] != cost ) continue ;
            for ( it = v [ nod ].begin() ; it != v [ nod ].end() ; ++ it )  {
            if ( d [ nod ] + (*it).s == d [ (*it).f ] || abs ( d [ nod ] + (*it).s - d [ (*it).f ] ) < ER ) {
                way [ (*it).f ] += way [ nod ] ;
                if ( way [ (*it).f ] > MOD )   way [ (*it).f ] -= MOD ;
            }   else
            if ( d [ nod ] + (*it).s < d [ (*it).f ] )  {
                d [ (*it).f ] = d [ nod ] + (*it).s ;
                q.push( mp ( (*it).f , d [ (*it).f ] ) ) ;
                way [ (*it).f ] = way [ nod ] ;
            }
    }
    }
}
int main () {
    int i , j , x , y , z ;
    in >> n >> m ;
    while ( m -- )  {
        in >> x >> y >> z ;
        v [ x ].pb ( mp ( y , log ( z ) ) ) ;
        v [ y ].pb ( mp ( x , log ( z ) ) ) ;
    }
    dijkstra() ;
    for ( i = 2 ; i <= n ; ++ i )   out << way [ i ] << ' ' ;
}