#include<fstream>
#include<vector>
#include<cmath>
#include<cstring>
#include<queue>
#define MOD 104659
#define EPS 0.0000000001
#define INF 2000000000.0
using namespace std;
ifstream fin("dmin.in");
ofstream fout("dmin.out");
int n, m, a, b, c, f[1005];
vector< pair<int, double> > v[1505];
pair<long double,long long> d[1505];
queue<int> q;
int main(){
    fin >> n >> m;
    for( int i = 1; i <= m; i++ ){
        fin >> a >> b >> c;
        v[a].push_back( make_pair( b, log(c) ) );
        v[b].push_back( make_pair( a, log(c) ) );
    }
    q.push( 1 );
    for( int i = 1; i <= n; i++ ){
        d[i].first = INF;
    }
    d[1].first = 0.0;
    d[1].second = 1;
    while( !q.empty() ){
        f[q.front()] = 1;
        int nod = q.front();
        for( int i = 0; i < v[nod].size(); i++ ){
            int vecin = v[nod][i].first;
            if( d[vecin].first - (d[nod].first + v[nod][i].second) > EPS ){
                d[vecin].first = d[nod].first + v[nod][i].second;
                d[vecin].second = d[nod].second;
                if( f[vecin] == 0 )
                    q.push( vecin );
                f[vecin] = 1;
            }else{
                if( d[vecin].first - (d[nod].first + v[nod][i].second) <= EPS && d[vecin].first - (d[nod].first + v[nod][i].second) >= -EPS ){
                    d[vecin].second = d[vecin].second + d[nod].second % MOD;
                    d[vecin].second %= MOD;
                    if( d[vecin].second < 0 ){
                        d[vecin].second += MOD;
                    }
                    f[vecin] = 1;
                    if( f[vecin] == 0 )
                        q.push( vecin );
                    f[vecin] = 1;
                }
            }
        }
        f[nod] = 0;
        q.pop();
    }
    for( int i = 2; i <= n; i++ ){
        fout << d[i].second << " ";
    }
    return 0;
}