#include<cstdio>
#define N 1501
#include<math.h>
#include<vector>
#define pb push_back
#define MOD 104659
#define INF 1<<20;
using namespace std;
short int n,m,x,y,coada[N];
int z,nr[N],rez[N];
double d[N];
bool viz[N];
vector<short int>a[N];
vector<double>c[N];
void citire()
{
	freopen("dmin.in","r",stdin);
	freopen("dmin.out","w",stdout);
	scanf("%hd%hd",&n,&m);
	for (int i=1; i<=m; ++i)
	{
		scanf("%hd%hd%d",&x,&y,&z);
		double g=log(z);
		a[x].pb(y);
		c[x].pb(g);
		a[y].pb(x);
		c[y].pb(g);
	}
}
void bf()
{
	int p=0,u=0;
	coada[u++]=1;
	nr[1]=1;
	viz[1]=true;
	while (u!=p)
	{
		x=coada[p++];
		viz[x]=false;
		size_t g=a[x].size();
		for (size_t i=0; i!=g; ++i)
		{
			y=a[x][i];
			double aux=d[x]+c[x][i],diff=d[y]-aux;
			if (diff>0)
			{
				d[y]=aux;
				nr[y]=nr[x];
				if (nr[y]>=MOD)
					nr[y]-=MOD;
				if (!viz[y])
				{
					viz[y]=true;
					coada[u++]=y;
				}
			}
			else
				if (diff==0)
				{
					nr[y]+=nr[x];
					if (nr[y]>=MOD)
						nr[y]-=MOD;
					if (!viz[y])
					{
						viz[y]=true;
						coada[u++]=y;
					}
				}
		}
		rez[x]=nr[x];
		nr[x]=0;
	}
}
void afis()
{
	for (int i=2; i<=n; ++i)
		printf("%d ",rez[i]);
}
int main()
{
	citire();
	for (int j=2; j<=n; ++j)
		{
			d[j]=INF;
			viz[j]=false;
			nr[j]=0;
		}
	bf();
	afis();
	return 0;
}