#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

#define maxN 1505
#define PB push_back
#define MKP make_pair
#define MOD 104659

const long long INF = 999999999;

vector <pair <int , int> > lista[maxN];
queue <int> Q;

int N , M , dmin[maxN];
long long cost[maxN];

int main ()
{
	freopen ("dmin.in" , "r" , stdin);
	freopen ("dmin.out" , "w" , stdout);
	
	scanf ("%d %d" , &N , &M);
	
	int a , b , c;
	
	for (int i = 1 ; i <= M ; ++i)
	{
		scanf ("%d %d %d" , &a , &b , &c);
		
		lista[a]. PB (MKP (b , c));
		lista[b]. PB (MKP (a , c));
	}
	
	for (int i = 1 ; i <= N ; ++i)
		cost[i] = INF;
	
	cost[1] = 1;
	Q.push (1);
	
	while (!Q.empty ())
	{
		int nod = Q.front ();
		
		Q.pop ();
		
		for (unsigned i = 0 ; i < lista[nod]. size () ; ++i)
		{
			
			int nodcur = lista[nod][i].first;
			int costmuc = lista[nod][i].second;
			
			
			
			if (cost[nod] * costmuc < cost[nodcur])
			{
				
				cost[nodcur] = cost[nod] * costmuc;
				dmin[nodcur] = max (dmin[nod] , 1);
				
				Q.push (nodcur);
			}
			
			else if (cost[nod] * costmuc == cost[nodcur])
				dmin[nodcur] = dmin[nodcur] % MOD + dmin[nod] % MOD;
				
		}
	}
	
	for (int i = 2 ; i <= N ; ++i)
		printf ("%d " , dmin[i]);
		
	
	/*cout << "\n";
	
	for (int i = 2 ; i <= N ; ++i)
		printf ("%lld " , cost[i]);*/

	
	return 0;
}