#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <cmath>
#define NMAX 1600
#define MOD 104659
#define PHI 0.000001
#define INF ( 1 << 29 )
#define mp make_pair

using namespace std ;

ofstream fout ( "dmin.out" ) ;

int N , M , dmin[NMAX] ;
double energy[NMAX] ;
vector < pair < int , double > > TT[NMAX] ;
queue < pair < int , double > > Q ;

double positive ( double x )
{
    return x > 0 ? x : -x ;
}

void read()
{
    int x , y , cost ;
    freopen ( "dmin.in" , "r" , stdin ) ;
    scanf ( "%d %d" , &N , &M ) ;
    for ( int i = 1 ; i <= M ; i++ )
    {
        scanf ( "%d %d %d" , &x , &y , &cost ) ; // logaritmam costul pentru a nu lucra cu numere mari si pentru ca log(a*b) = log a + log b
        TT[x].push_back( mp( y , log(cost) ) ) ;
        TT[y].push_back( mp( x , log(cost) ) ) ;
    }
    for ( int i = 2 ; i <= N ; i++ )
    energy[i] = INF ;
}

void bellman_ford()
{
    dmin[1] = 1 ;
    Q.push( mp( 1 , 0 ) ) ;
    while ( !Q.empty() )
    {
        int node = Q.front().first ;
        double cost = Q.front().second ;
        if ( cost - energy[node] >= PHI )
        continue ;
        Q.pop() ;
        for ( vector < pair < int , double > > :: iterator it = TT[node].begin() ; it != TT[node].end() ; ++it )
        {
            double new_cost = cost + it->second ;
            if ( energy[it->first] < new_cost )
            continue ;
            if ( positive( energy[it->first] - new_cost ) <= PHI )
            dmin[it->first] = ( dmin[node] + dmin[it->first] ) % MOD ;
            else
            {
                if ( new_cost < energy[it->first] )
                {
                    energy[it->first] = new_cost ;
                    dmin[it->first] = dmin[node] ;
                    Q.push( mp( it->first , energy[it->first] ) ) ;
                }
            }

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


int main()
{
    read() ;
    bellman_ford() ;
    return 0;
}