#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 1505;
const int MOD = 104659;
const double INF = 20000000;

typedef pair<double,int> pii;

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

bool _egal( double a, double b ) {
    return abs( a - b ) <= 1e-10;
}

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

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

       double c = log(d);

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

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

void Do()
{
    for( int i = 1; i <= N; ++i )
      d[i] = INF;

    priority_queue <pii, vector<pii>, greater<pii> > Q;

    d[1] = 0;
    nrd[1] = 1;
    Q.push( { 0, 1 } );

    int w, nod;
    while( !Q.empty() ) {
        nod = Q.top().second;
        Q.pop();

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

           if( _egal( d[w], d[nod] + Cost[nod][i] ) ) {
             nrd[w] = ( 1LL * nrd[w] + nrd[nod] ) % MOD;
             //Q.push( { d[w], w } );
           }
           else
             if( d[w] > d[nod] + Cost[nod][i] ) {
                d[w] = d[nod] + Cost[nod][i];
                nrd[w] = nrd[nod];

                Q.push( { d[w], w } );
             }
        }
    }

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

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

    return 0;
}