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

using namespace std;

#define MOD 104659
#define maxN 1505
#define INF (1<<29)
#define eps 1e-10

FILE*f=fopen("dmin.in","r");
FILE*g=fopen("dmin.out","w");

int n,m,i,j,x,y,cst,H[maxN],Poz[maxN],Nr[maxN],nod,nodvcn,L,Viz[maxN],nodbst; 
vector< pair<int,double> >G[maxN]; double lg,D[maxN],cstvcn,bst;

inline void citire () {
	
	fscanf(f,"%d %d",&n,&m);
	
	for ( i = 1 ; i <= m ; ++i ){
		fscanf(f,"%d %d %d",&x,&y,&cst);
		lg = log(cst);
		G[x].push_back(make_pair(y,lg));
		G[y].push_back(make_pair(x,lg));
	}
}

inline void swap ( int &a, int &b ){
	int aux = a;
	a = b;
	b = aux;
}

inline double aabs ( double j ){
	if ( j < 0 )
		return -j;
	return j;
}


inline void urca ( int poz ){
	
	while ( poz && D[H[poz>>1]] > D[H[poz]] ){
		swap(H[poz>>1],H[poz]);
		swap(Poz[H[poz>>1]],Poz[H[poz]]);
		poz = poz >> 1;
	}
}

inline void coboara ( int x ){
	int y = INF;
	
	while ( x != y ){
		y = x;
		if ( (y<<1) <= L && D[H[y<<1]] < D[H[x]] )	x = y << 1;
		if ( (y<<1) + 1 <= L && D[H[(y<<1)+1]] < D[H[x]] ) x = (y<<1) + 1;
		swap(H[x],H[y]);
		swap(Poz[H[x]],Poz[H[y]]);
	}
}


inline void insert_heap( int nod ){
	H[++L] = nod;
	Poz[nod] = L;
	urca(L);
}

inline int delete_first( ){
	int nod = H[1];
	swap(H[1],H[L--]);
	coboara(1);
	Poz[nod] = 0;
	return nod;
}


inline void dijkstra () {
	
	for ( Nr[1] = 1, i = 2 ; i <= n ; ++i ){
		D[i] = INF;
	}
	
	insert_heap(1);
	
	while ( L ){
		nod = delete_first();
		
		for ( i = 0 ; i < G[nod].size() ; ++i ){
			nodvcn = G[nod][i].first; cstvcn = G[nod][i].second;
			
			if ( aabs(D[nod] + cstvcn - D[nodvcn] ) < eps ){
				Nr[nodvcn] += Nr[nod];
				if ( Nr[nodvcn] >= MOD )
					Nr[nodvcn] -= MOD;
			}
			else{
				if ( D[nod] + cstvcn - D[nodvcn] < eps ){
					D[nodvcn] = D[nod] + cstvcn;
					if ( Poz[nodvcn] )
						urca(Poz[nodvcn]);
					else
						insert_heap(nodvcn);
					Nr[nodvcn] = Nr[nod];
				}
			}
		}
		
	}
	
	
	/*for ( i = 1 ; i <= n ; ++i ){
		bst = INF;
		for ( j = 1 ; j <= n ; ++j ){
			if ( !Viz[j] && D[j] < bst )
				nodbst = j,bst = D[j];
		}
		Viz[nodbst] = 1; nod = nodbst;
		for ( j = 0 ; j < G[nodbst].size() ; ++j ){
			nodvcn = G[nod][j].first; cstvcn = G[nod][j].second;
			
			if ( aabs(D[nod] + cstvcn - D[nodvcn] ) < eps ){
				Nr[nodvcn] += Nr[nod];
				if ( Nr[nodvcn] >= MOD )
					Nr[nodvcn] -= MOD;
			}
			else{
				if ( D[nod] + cstvcn - D[nodvcn] < eps ){
					D[nodvcn] = D[nod] + cstvcn;
					Nr[nodvcn] = Nr[nod];
				}
			}
			
		}
	}
	*/
	for ( i = 2 ; i <= n ; ++i ){
		fprintf(g,"%d ",Nr[i]);
	}
}


int main () {
	
	citire();
	
	dijkstra();
	
	fclose(f);
	fclose(g);
	
	return 0;
}