#include <iostream>
#include <stdio.h>
#include <vector>
#include <math.h>

#define EPS 1e-10
using namespace std;


const double INF = 1000000.0;

vector<int> fii[1501];
vector<double> cost[1501];

int n,m,lh;

double distmin[1501];
int mod[1501];
int heap[1501];
int pozheap[1501];

void pop( int x );
void push( int x );

int main()
{
    int i,j;
    int nodc;
    int a,b,c;
    freopen("dmin.in","r",stdin);
    freopen("dmin.out","w",stdout);
    
    scanf("%d %d\n", &n, &m);
    
    for ( i = 1; i <= m; i++ )
    {
		scanf("%d %d %d\n", &a, &b, &c);
		fii[a].push_back(b);
		fii[b].push_back(a);
		cost[a].push_back( (double) log(c) );		
		cost[b].push_back( (double) log(c) );
		if ( i <= n )
		{
	    	heap[ i ] = i;
	    	pozheap[ i ] = i;
	    	distmin[ i ] = INF;
		}
    }
    
    distmin[ 1 ] = 0.0;
    mod[ 1 ] = 1;
    lh = n;
    
    while ( lh )
    {
		nodc = heap[ 1 ];
	
		for ( i = 0; i < fii[ nodc ].size(); i++ )
	    	if ( distmin[ fii[nodc][i] ] - ( distmin[ nodc ] + cost[nodc][i] ) > EPS   )
	    	{
				distmin[ fii[nodc][i] ] = distmin[nodc] + cost[nodc][i];
				mod[ fii[ nodc ][ i ] ] = mod[ nodc ];
				pop( pozheap[ fii[ nodc ][ i ] ] );
	    	}
	    	else 
	    		if ( fabs( distmin[ fii[nodc][i] ] - ( distmin[ nodc ] + cost[ nodc ][ i ] ) ) <= EPS)
	    		{
					mod[ fii[ nodc ][ i ] ] += mod[ nodc ];
					mod[ fii[ nodc ][ i ] ] %= 104659;
	    		}
		heap[1] = heap[lh];
		pozheap[ heap[1] ] = 1;
		lh--;
		
		push(1);
    }
    
    for ( i = 2; i <= n; i++ )
		printf("%d ", mod[i]);
        
    fclose(stdin);
    fclose(stdout);
    
    return 0;
}
		
void pop( int x )
{
    int aux;
    while ( x > 0 &&  distmin[ heap[x] ] - distmin[ heap[x/2] ] < EPS)
    {
		aux = heap[x];
		heap[x] = heap[x/2];
		heap[x/2] = aux;
		
		pozheap[ heap[x] ] = x;
		pozheap[ heap[x/2] ] = x/2;
		
		x=x/2;
    }
}

void push( int x )
{
    int q=0,aux;
    while ( q!=x )
    {
		q=x;
		
		if ( 2*q <= lh && distmin[ heap[x] ] - distmin[ heap[2*q] ] > EPS)
	    	x = 2*q;
		if ( 2*q+1 <= lh && distmin[ heap[x] ] - distmin[ heap[2*q+1] ] >EPS )
	    	x = 2*q+1;
		
		aux = heap[x];
		heap[x] = heap[q];
		heap[q] = aux;
		
		pozheap[ heap[x] ] = x;
		pozheap[ heap[q] ] = q;
		
		x=q;
    }
}