#include <stdio.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <queue>
#include <set>
#define MOD 104659
#define NMAX 1505
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define INF 2000000000
#define eps 1e-10
using namespace std;
int n,m,C[NMAX],var[NMAX];
vector < pair<int,int> >v[NMAX];
double CF[NMAX],cost[NMAX];
char viz[NMAX];
queue < pair <double,int> > Q;
void read()
{
	scanf("%d%d",&n,&m);
	int i,x,y;
	for (i=1; i<=m; i++)
	{
		scanf("%d%d%d",&x,&y,&C[i]);
		v[x].pb(mp(y,i));
		v[y].pb(mp(x,i));
	}
}
void init()
{
	int i;
	for (i=2; i<=n; i++)
		cost[i]=INF;
}
inline double modul(double x)
{
	return x<0 ? -x : x;
}
void apel(int nod)
{
	int i,y,z;
	for (i=0; i<v[nod].size(); i++)
	{
		y=v[nod][i].f; z=v[nod][i].s;
		if (modul(cost[y]+CF[z]-cost[nod])<=eps)
		{
			if (!viz[y])
				apel(y);
			var[nod]+=var[y];
			if (var[nod]>=MOD)
				var[nod]-=MOD;
		}
	}
	viz[nod]=1;
}
void solve()
{
	int i,x,y,z;
	double val;
	for (i=1; i<=m; i++)
		CF[i]=log10(C[i]);
	var[1]=1;  viz[1]=1;
	init();
	Q.push(mp(0,1));
	while(!Q.empty())
	{
		val = Q.front().f, x = Q.front().s;
		Q.pop();
		for (i=0; i<v[x].size(); i++)
		{
			y=v[x][i].f; z=v[x][i].s;
			if (cost[x]+CF[z]<cost[y])
			{
				cost[y]=cost[x]+CF[z];
				Q.push(mp(cost[y],y));
			}
		}
	}
	for (i=2; i<=n; i++)
		if (!viz[i])
			apel(i);
}
void show()
{
	int i;
	for (i=2; i<=n; i++)
		printf("%d ",var[i]);
	printf("\n");
}
int main()
{
	freopen("dmin.in","r",stdin);
	freopen("dmin.out","w",stdout);
	read();
	solve();
	show();
	return 0;
}