#include<fstream.h>
#include<math.h>
#define _DIM_ 1501
#define modulo 104659
#define eps 0.00001


ifstream f("dmin.in");
ofstream g("dmin.out");
typedef struct _lista
	{
	int x;
	double c;
	_lista *urm;
	}*Lista;
typedef struct _nod
	{
	Lista l;
	}Nod;
Nod V[_DIM_];
double c[_DIM_];
long mod[_DIM_];
int v[_DIM_],coada[_DIM_],n,m,p,u;
void adauga(int x,int y,int cost)
	{
	Lista nou=new _lista;
	nou->x=y;nou->c=cost;
	nou->urm=V[x].l;
	V[x].l=nou;
	}
void citire()
	{
	int i,cost,x,y;
	f>>n>>m;
	for(i=1;i<=m;i++)
		f>>x>>y>>cost,adauga(x,y,cost),adauga(y,x,cost);
	}
void getmin(int p,int u)
	{
	int i,aux;
	double min=c[coada[p]];
	int minpoz=p;
	for(i=p+1;i<=u;i++)
		if(min>c[coada[i]])min=c[coada[i]],minpoz=i;
	aux=coada[p],coada[p]=coada[minpoz],coada[minpoz]=aux;
	}
void dijkstra(int k)
	{
	Lista i;
	p=u=1;coada[1]=k;
	v[k]=1;c[k]=0;
	while(p<=u)
		{
		getmin(p,u);
		k=coada[p];
		for(i=V[k].l;i;i=i->urm)
			if(!v[i->x])
				coada[++u]=i->x,v[i->x]=1,mod[i->x]=mod[k],mod[i->x]%=modulo,
							c[i->x]=c[k]+log(i->c);

			else
				{
				if(c[i->x]>c[k]+log(i->c))
					c[i->x]=c[k]+log(i->c),mod[i->x]=mod[k],mod[i->x]%=modulo;
				if(abs(c[i->x]-(c[k]+log(i->c)))<eps)
					mod[i->x]+=mod[k],mod[i->x]%=modulo;
				}
		p++;
		}
	}
int main()
{
int i;
Lista j;
citire();f.close();
mod[1]=1;
dijkstra(1);
for(i=2;i<=n;i++)
	g<<mod[i]%modulo<<" ";
g.close();
return 0;
}