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

const double EPSILON=0.0000001;
const double INFINIT=1000000;
const long int MAXN=1500;
const long int MODULO=104659;

typedef struct NODL{long int inf; double cost; NODL *next;};
struct {NODL *prim,*ultim;} ladiac[MAXN+1];
long int n,m;
double r[MAXN+1];long int heaplen,nr[MAXN+1],heap[MAXN+1],index[MAXN+1];

void add(long int loc, long int inf, double cost)
{
NODL *p;
p=(NODL*) malloc (sizeof(NODL));
(*p).next=NULL;
(*p).inf=inf;
(*p).cost=cost;
if (ladiac[loc].prim==NULL)
	{
	ladiac[loc].prim=p;
	ladiac[loc].ultim=p;
	}
else
	{
	(*ladiac[loc].ultim).next=p;
	ladiac[loc].ultim=p;
	}
}

void citire()
{
FILE *f=fopen("dmin.in","r");
fscanf(f,"%ld%ld",&n,&m);
long int i,aa,bb,cc;double cost;
for (i=1;i<=m;i++)
	{
	fscanf(f,"%ld%ld%ld",&aa,&bb,&cc);
	cost=(double)log(cc);
	add(aa,bb,cost);
	add(bb,aa,cost);
	}
fclose(f);
}

double modul(double a) {if (a>=0) return a; return -a;}
int egal(double a, double b) {if (modul(a-b)<=EPSILON) return 1; return 0;}
int mai_mare(double a, double b) {if (a-b>EPSILON||(egal(a,b)&&a-b>0)) return 1; return 0;}
int mai_mic(double a, double b) {if (mai_mare(a,b)||egal(a,b)) return 0; return 1;}

void float_heap(long int i)
{
long int aux;
while (i/2&&mai_mare(r[heap[i/2]],r[heap[i]]))
	{
	aux=heap[i];
	heap[i]=heap[i/2];
	heap[i/2]=aux;
	index[heap[i]]=i;
	index[heap[i/2]]=i/2;
	i/=2;
	}
}

int submerge_heap(long int i)
{
long int min,aux;
do
	{
	min=i;
	if (i*2<=heaplen&&mai_mic(r[heap[i*2]],r[heap[min]])) min=i*2;
	if (i*2+1<=heaplen&&mai_mic(r[heap[i*2+1]],r[heap[min]])) min=i*2+1;
	if (i==min) return 0;
	aux=heap[i];
	heap[i]=heap[min];
	heap[min]=aux;
	index[heap[i]]=i;
	index[heap[min]]=min;
	}
while (1);
}

void extract_heap(long int &x)
{
x=heap[1];
index[heap[1]]=0;
heap[1]=heap[heaplen];
index[heap[1]]=1;
heap[heaplen]=0;
heaplen--;
submerge_heap(1);
}

void update(long int nod)
{
NODL *p=ladiac[nod].prim;
long int i;
while (p)
	{
	i=(*p).inf;
	if (index[i]!=0)
		{
		if (mai_mare(r[i],r[nod]+(*p).cost))
			{
			r[i]=r[nod]+(*p).cost;
			float_heap(index[i]);
			}
		}
	p=(*p).next;
	}
}

void create_heap()
{
long int i;
for (i=2;i<=n;i++) r[i]=INFINIT;
NODL *p=ladiac[1].prim;
while (p)
	{
	r[(*p).inf]=(*p).cost;
	p=(*p).next;
	}
for (i=2;i<=n;i++)
	{
	heap[++heaplen]=i;
	index[heap[heaplen]]=heaplen;
	float_heap(heaplen);
	}
}

void find_pred(long int a)
{
NODL *p=ladiac[a].prim;
while (p)
	{
	if (egal(r[(*p).inf]+(*p).cost,r[a]))
		{
		nr[a]+=nr[(*p).inf];
		nr[a]%=MODULO;
		}
	p=(*p).next;
	}
}

void dijkstra()
{
long int a;
create_heap();
nr[1]=1;
while (heaplen)
	{
	extract_heap(a);
	find_pred(a);
	update(a);
	}
}

void scrie()
{
long int i;
FILE *g=fopen("dmin.out","w");
if (n>1) fprintf(g,"%ld",nr[2]);
for (i=3;i<=n;i++) fprintf(g," %ld",nr[i]);
fprintf(g,"\n");
fcloseall();
}

int main()
{
citire();
dijkstra();
scrie();
return 0;
}