#include <stdio.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <queue>
#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 0.0000000001
using namespace std;
int n,m,C[NMAX],var[NMAX],var_f[NMAX];
vector < pair<int,int> >v[NMAX];
double CF[NMAX],cost[NMAX];
queue <int> Q,Q2;
char in[NMAX];
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 solve()
{
	int i,x,y,z;
	for (i=1; i<=m; i++)
		CF[i]=log10((double)C[i]);
	Q.push(1); var[1]=1; in[1]=1; 
	init();
	while (!Q.empty())
	{
		x=Q.front();
		in[x]=0;
		Q.pop();
		for (i=0; i<v[x].size(); i++)
		{
			y=v[x][i].f; z=v[x][i].s;
			if (modul(cost[x]+CF[z]-cost[y])<=eps)
			{
				var[y]+=var[x];
				var_f[y]+=var[x];
				if (var[y]>=MOD)
					var[y]%=MOD;
				if (var_f[y]>=MOD)
					var_f[y]%=MOD;
				Q.push(y);
			}
			if (cost[x]+CF[z]<cost[y])
			{
				var[y]=var[x]; var_f[y]=var[x];
				cost[y]=cost[x]+CF[z];
				if (!in[y])
					Q.push(y),in[y]=1;
			}
		}
		var[x]=0;
	}
}
void show()
{
	int i;
	for (i=2; i<=n; i++)
		printf("%d ",var_f[i]);
	printf("\n");
}
int main()
{
	freopen("dmin.in","r",stdin);
	freopen("dmin.out","w",stdout);
	read();
	solve();
	show();
	return 0;
}