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

using namespace std;

const double EPS = 1e-7;
vector<int> fii[1501];
vector<double> cost[1501];
int mod[1501];
int nodc;

int heap[1501];
int pozheap[1501];
int lh;
double dist[1501];

int n,m;


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

double absv( double x )
{
	if ( x < 0 ) return ( -1*x );
	return x;
}

int main()
{
	int a,b;
	double c=0;
	int i;
	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 %lf\n", &a, &b ,&c);
		fii[a].push_back( b );
		fii[b].push_back( a );
		cost[a].push_back( log( c ) );
		cost[b].push_back( log( c ) );
	}

	for ( i = 1; i <= n; i++ )
	{	
		heap[i] = i;
		pozheap[ i ] = i;
		dist[i] = 10000000;
	}
	dist[1] = 0;
	mod[1] = 1;
	lh = n;

	while ( lh )
	{
		nodc = heap[1];
		for ( i = 0; i < fii[ nodc ].size(); i++ )
			if ( dist[ nodc ] + cost[ nodc ][ i ] < dist[ fii[nodc][i] ] )
			{
				dist[ fii[nodc][i] ] = dist[ nodc ] + cost[ nodc ][ i ];
				mod[ fii[nodc][i] ] = mod[ nodc ];
				pop( pozheap[ fii[nodc][i] ] );
			}
			else
			if ( absv( dist[ nodc ] + cost[ nodc ][ i ] - dist[ fii[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] );
	printf("\n");
		
	fclose(stdin);
	fclose(stdout);

	return 0;
}

void pop( int x )
{
	int aux;
	while ( x > 1 && dist[ heap[x] ] < dist[ heap[x/2] ] )
	{
		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 aux,q=0;
	while ( q != x )
	{
		q=x;
		if ( q*2 <= lh && dist[ heap[x] ] > dist[ heap[q*2] ] )
			x = q*2;
		if ( q*2+1 <= lh && dist[ heap[x] ] > dist[ heap[q*2+1] ] )
			x = q*2+1;

		aux = heap[q];
		heap[q] = heap[x];
		heap[x] = aux;

		pozheap[ heap[q] ] = q;
		pozheap[ heap[x] ] = x;
	}
}