#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-20;

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;
}