#include<stdio.h>
#define fin "dmin.in"
#define fout "dmin.out"
#define Nmax 1501
#define Mmax 2501
#define Mod 104659
#define Inf 2134000000
int cost[Nmax],nrsol[Nmax],v[Nmax][Mmax],v_cost[Nmax][Mmax];
int n,m,st[Nmax];
FILE *in,*out;

void go() {
int i,nod,min,poz,x;
	
	min=Inf;
	
	for (i=1;i<=st[0];++i) {
		//printf("%i ",st[i]);
		if(cost[st[i]]<min) {
			nod=st[i];
			poz=i;
			min=cost[st[i]];
		}
	}
	//printf("\n");
	//for (i=1;i<=n;++i) printf("%i ",cost[i]);
	//printf("min: %i\n\n",nod);

	st[poz]=st[st[0]];
	st[0]--;

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

			else 
			if (cost[x]>(cost[nod]+v_cost[nod][i])) {
				
				cost[x]=cost[nod]+v_cost[nod][i];
				nrsol[x]=nrsol[nod];
			}
	}

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

int main() {
int i,j,x,y,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%i",&x,&y,&c);
		v[x][0]++;
		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;
}