#include <bits/stdc++.h>

using namespace std;

ifstream fin( "dmin.in" );
ofstream fout( "dmin.out" );

const int NMAX = 1502;
const int MOD = 104659;
const long double INF = 100000000;
const double error = 0.00005;

int N, M;
vector <int> Ad[NMAX];
vector <int> Cost[NMAX];

long double d[NMAX];
int nr_d[NMAX];

void Read()
{
    fin >> N >> M;

    int a, b, c;

    for( int i = 1; i <= M; ++i ) {
        fin >> a >> b >> c;

        Ad[a].push_back( b );
        Cost[a].push_back( c );

        Ad[b].push_back( a );
        Cost[b].push_back( c );
    }
}

void Do()
{
    priority_queue < pair<long double,int>, vector< pair<long double,int> >, greater<pair<long double,int> > > Heap;

    for( int i = 2; i <= N; ++i )
       d[i] = INF;

    d[1] = 1;

    nr_d[1] = 1;

    Heap.push( { 0, 1 } );

    while( !Heap.empty() )
    {
        int u = Heap.top().second;

        Heap.pop();

        for( int i = 0; i < Ad[u].size(); ++i )
        {
            int w = Ad[u][i];

            if( d[w] > (long double)d[u] + log( Cost[u][i] ) ) {
                d[w] = (long double)d[u] + log( Cost[u][i] );
                nr_d[w] = nr_d[u];

                Heap.push( { d[w], w } );
            }
            else
              if( abs( d[w] - (long double)d[u] - log( Cost[u][i] ) ) < error )
              {
                  nr_d[w] = ( 1LL * nr_d[w] + nr_d[u] ) % MOD;
              }
        }
    }

    for( int i = 2; i <= N; ++i )
      fout << nr_d[i] << ' ';
}

int main()
{
    Read();
    Do();

    return 0;
}