#include<cstdio>
#define N 1501
#include<math.h>
#include<vector>
#include<bitset>
#define pb push_back
#define MOD 104659
#define INF 1<<30;
using namespace std;
short int n,m,x,y,coada[N*N];
int z,nr[N],rez[N];
double d[N];
bitset<N> viz;
const double eps=1e-8;
const double eps1=eps*(-1);
vector<short int>a[N],ap(N,0);
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=log10(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]=1;
	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>=eps)
			{
				d[y]=aux;
				if (!viz[y])
				{
					viz[y]=true;
					coada[u++]=y;
				}
			}
		}
	}
}
void afis()
{
	for (int i=2; i<=n; ++i)
		printf("%d ",nr[i]);
}
void df(int x)
{
	viz[x]=1;
	size_t g=a[x].size();
	for (size_t i=0; i<g; ++i)
	{
		double diff=d[x]-d[a[x][i]]-c[x][i];
		if(diff<=eps&&diff>=eps1)
		{
			
			if (!viz[a[x][i]])
				df(a[x][i]);
			nr[x]+=nr[a[x][i]];
			if (nr[x]>=MOD)
				nr[x]-=MOD;
		}
	}
}
int main()
{
	citire();
	for (int j=2; j<=n; ++j)
		d[j]=INF;
	bf();
	viz.reset();
	nr[1]=1;
	for (int i=2; i<=n; ++i)
		if (!viz[i])
			df(i);
	afis();
	/*printf("\n");
	for (int j=2; j<=n; ++j)
		printf("%lf ",d[j]);*/
	return 0;
}