#include <bits/stdc++.h>
using namespace std;
fstream in ( "dmin.in" , ios::in );
fstream out( "dmin.out", ios::out );
const int DIM = 1505;
const int MOD = 104659;
const int INF = 0x3f3f3f3f;
const long double EPS = 1e-10;
int cnt[DIM];
long double dst[DIM];
vector<pair<long double, int>> edg[DIM];
priority_queue< pair<long double, int>,
               vector <pair<long double, int>>,
               greater<pair<long double, int>>> prq;
inline int sgn( long double x ) {
    if( fabs( x ) < EPS )
        return 0;
    return ( x < 0 ) ? -1 : 1;
}
int main( void ) {
    ios::sync_with_stdio( false );
    int n, m;
    in >> n >> m;
    for( int i = 1; i <= m; i ++ ) {
        int x, y, z;
        in >> x >> y >> z;
        edg[x].push_back( make_pair( log10( z ), y ) );
        edg[y].push_back( make_pair( log10( z ), x ) );
    }
    fill( dst + 2, dst + n + 1, INF ); cnt[1] = 1;
    for( prq.push( make_pair( 0, 1 ) ); !prq.empty(); prq.pop() ) {
        pair<long double, int> x = prq.top();
        if( sgn( x.first - dst[x.second] ) > 0 )
            continue;
        for( pair<long double, int> y : edg[x.second] ) {
            if( sgn( dst[y.second] - ( dst[x.second] + y.first ) ) > 0 ) {
                dst[y.second] = dst[x.second] + y.first;
                cnt[y.second] = cnt[x.second];
                prq.push( make_pair( dst[y.second], y.second ) );
            }
            else {
                if( sgn( dst[y.second] - ( dst[x.second] + y.first ) ) == 0 )
                    cnt[y.second] = ( cnt[y.second] + cnt[x.second] ) % MOD;
            }
        }
    }
    for( int i = 2; i <= n; i ++ )
        out << cnt[i] << " ";
    out << endl;
    return 0;
}