#include<fstream>
#include<iostream>
#include<cmath>
using namespace std;
struct nod
{
	int vf;
	unsigned int val;
	nod *next;
};
nod *g[1510];
#define nn 1510
#define inn 1<<30
int v[nn],nr[nn],t[nn];
int n,m;
double d[nn],eps=1e-10;
void adauga(int a,int b,unsigned int c)
{
	nod *t=new nod;
	t->vf=b;
	t->val=c;
	t->next=g[a];
	g[a]=t;
}
int main()
{
	int a,b;
	unsigned int c;
	ifstream fin("dmin.in");
	fin>>n>>m;
	for(;m;--m)
	{
		fin>>a>>b>>c;
		adauga(a,b,c);
		adauga(b,a,c);
	}
	for(int i=0 ; i<=n ; ++i)
		d[i]=inn, v[i]=0, nr[i]=0;
	d[1]=0, v[1]=1, nr[1]=1;
	for(nod *p=g[1] ; p ; p=p->next)
		if(v[p->vf]==0)
			d[p->vf] = log(p->val), nr[p->vf]=nr[1];
	for(int kkk=1;kkk<n;++kkk){
	
	int dmin=0;
	for(int i=1;i<=n;++i)
		if(v[i]==0 && d[i]<d[dmin])
			dmin=i;
	if(dmin==0)
		break;
	v[dmin]=1;
	for(nod *p=g[dmin];p;p=p->next)
	{
		int i=p->vf;
		if(!v[i])
			if(d[i]>d[dmin]+log(p->val)+eps)
			{
				d[i]=d[dmin]+log(p->val);
				nr[i]=nr[dmin];
			}
			else
				if( abs(d[i]-(d[dmin]+log(p->val) ))<eps)
				{
					nr[i]=(nr[i]+nr[dmin])%104659;
				}
	}
}
	ofstream fout("dmin.out");
	for(int i=2;i<=n;++i)
		fout<<nr[i]<<" ";
	return 0;
}