#include<fstream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<limits.h>
#define inf numeric_limits<double>::max()
using namespace std;
ifstream f("dmin.in");
ofstream g("dmin.out");
int n,m,k,i,x,y,j,heapn,where;
double z,cat,dif,mymin[1501];
int minim,p,dest[1501],nr[1501],d[1501];
vector< pair<int,double> > a[1501]; //first=dest,second=cost
double eps=1e-10;
void downheap(int p,int heapn){
	int l,r;
	while((p<<1)<=heapn){
		minim=p;
		l=p<<1;
		r=l+1;
		if(mymin[d[minim]]>mymin[d[l]])
			 minim=l;
		if(r<=heapn&&mymin[d[minim]]>mymin[d[r]])
			 minim=r;
		if(minim!=p){
			 int t=d[p];
			 d[p]=d[minim];dest[d[minim]]=p;
			 d[minim]=t;dest[t]=minim;
			 p=minim;
		}
		else break;
	}
}
double absm(double x){
	if(x<0)
		return -x;
	return x;
}
void upheap(int x,int p){
	int t;
	t=p>>1;
	while(p>1 && mymin[x]<mymin[d[t]]){
		    d[p]=d[t];
			dest[d[t]]=p;
			p=t;t=t>>1;		
		
	  	}
	d[p]=x;dest[x]=p;
}

int main(){
f>>n>>m;
for(i=1;i<=m;i++){
	f>>x>>y>>z;
	z=log(z);
	a[x].push_back(make_pair(y,z));
	}
for(i=2;i<=n;i++){
	mymin[i]=inf;
}

for(i=0;i<=(int)a[1].size()-1 ;i++){
	heapn++;
	mymin[a[1][i].first]=a[1][i].second;
	nr[a[1][i].first]=1;
	upheap(a[1][i].first,heapn);
}

while (heapn){
    p=d[1];
	d[1]=d[heapn];
	dest[d[heapn]]=1;
	heapn--;
	downheap(1,heapn);
    for(i=0;i<=(int)a[p].size()-1;i++){
	  where=a[p][i].first,cat=a[p][i].second,dif=mymin[p]+cat-mymin[where],dif=absm(dif);
	  if( dif < eps )
		   nr[where]+=nr[p],nr[where]%=104659;
	  else 
	  if(  mymin[where] -(mymin[p] + cat) > eps ){
		     mymin[where]=mymin[p]+cat,nr[where]=nr[p];
		if(dest[where]==0)
			heapn++,upheap(where,heapn);
		else
		    upheap(where,dest[where]);
	  }
}
}
for(i=2;i<=n;i++)	
	 g<<nr[i]<<" ";

return 0;
}