#include<cstdio>
#include<vector>
#include<cmath>
#define pb push_back
#define mp std::make_pair<int,double>
std::vector<std::pair<int,double> > a[1501];
int n,m,nr[1501],h[1501],p[1501],i;
double d[1501],lg;
const double oo=50000.0;
const int mod=104659;
const double precizie=1e-10;
double _abs(double a)
{
	if(a<0) return -a;
	return a;
}
inline void swap(int x,int y)
{
	int aux;
	aux=h[y];h[y]=h[x];h[x]=aux;
	p[h[x]]=x;p[h[y]]=y;
}
void down(int x)
{
	int st,dr;
	st=x<<1;dr=st+1;
	if(st<=m)
	{
		if(dr<=m && d[h[dr]]<d[h[st]]) st=dr;
		if(d[h[x]]>d[h[st]]) 
		{
			swap(x,st);
			down(st);
		}
	}
}
int get()
{
	swap(1,m);
	m--;
	down(1);
	return h[m+1];
}
void up(int x)
{
	if(x==1) return;
	int t=x>>1;
	if(d[h[t]]>d[h[x]])
	{
		swap(x,t);
		up(t);
	}
}
int main()
{
	freopen("dmin.in","r",stdin);
	freopen("dmin.out","w",stdout);
	scanf("%d %d",&n,&m);
	for(int x,y,z,i=1;i<=m;++i)
	{
		scanf("%d %d %d",&x,&y,&z);
		lg=log((double)z);
		a[x].pb(mp(y,z));
		a[y].pb(mp(x,z));
	}
	d[1]=(double)0.0;nr[1]=1;h[1]=1;p[1]=1;m=n;
	for(i=2;i<=n;i++) d[i]=oo,h[i]=i,p[i]=i;
	int x,y;
	double c;
	while(1)
	{
		if(m==0) break;
		x=get();
		if(d[x]==oo) break;
		for(i=0;i<a[x].size();i++)
		{
			y=a[x][i].first;
			c=a[x][i].second;
			if((d[y]-d[x]-c)>precizie)
			{
				d[y]=d[x]+c;
				nr[y]=nr[x];
				up(p[y]);
			}
			else
				if(_abs(d[y]-d[x]-c)<=precizie)
					nr[y]=(nr[y]+nr[x])%mod;
		}
	}
	for(i=2;i<=n;i++)
		printf("%d ",nr[i]);
	fclose(stdout);
	return 0;
}