#include<math.h>
#include<stdio.h>
#define fin "dmin.in"
#define fout "dmin.out"
#define Nmax 1501
#define Mmax 2501
#define Mod 104659
#define Eps 1e-10
int nrsol[Nmax],viz[Nmax],v[Nmax][Mmax];
double cost[Nmax],v_cost[Nmax][Nmax];
int n,m,st[Nmax];
FILE *in,*out;

double absf(double a) {
	if (a<0) return -a;
	return a;
}

void go() {
int i,nod,poz,x;
double min,a,b;
	
	min=cost[st[1]]; nod=st[1]; poz=1;
	
	for (i=2;i<=st[0];++i) {
		a=cost[st[i]];
		if(a<min) {
			nod=st[i];
			poz=i;
			min=cost[st[i]];
		}
	}
	st[poz]=st[st[0]];
	st[0]--;
	viz[nod]=1;

	for (i=1;i<=v[nod][0];++i) {
		x=v[nod][i]; a=cost[x];
		b=cost[nod]+v_cost[nod][i];
		if (!viz[x])
		if (!a) {
			cost[x]=b;
			nrsol[x]=nrsol[nod];
			st[++st[0]]=x;
		}
		else {
			if (absf(a-b)<=Eps) {
				
				nrsol[x]=nrsol[x]+nrsol[nod];
				if (nrsol[x]>=Mod) nrsol[x]=nrsol[x]-Mod;
			
			}

			else 
			
			if (absf(a-b)>Eps) {
				
				cost[x]=b;
				nrsol[x]=nrsol[nod];
			}
		}
	}

	if (st[0]) go();
}

int main() {
int i,j,x,y;
double c;
	in=fopen(fin,"r"); out=fopen(fout,"w");
	fscanf(in,"%i%i",&n,&m);
	
	for (i=1;i<=m;++i) {
		fscanf(in,"%i%i%lf",&x,&y,&c);
		v[x][0]++; c=log(c);
		v[y][0]++;
		v[x][v[x][0]]=y; v_cost[x][v[x][0]]=c;
		v[y][v[y][0]]=x; v_cost[y][v[y][0]]=c;
	}
	
	nrsol[1]=1;
	st[0]=st[1]=1;

	go();

	for (i=2;i<=n;++i) { 
		if (i!=2) fprintf(out," ");
		fprintf(out,"%i",nrsol[i]);
	}
	
	fprintf(out,"\n");

	fclose(in); fclose(out);

	return 0;
}