#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 20000
#define eps 1e-10
using namespace std;
int n,m,C[NMAX],var[NMAX];
vector < pair<int,int> >v[NMAX];
long double CF[NMAX],cost[NMAX];
queue <int> Q,Q2;
char in[NMAX];
set <pair <long double,int> > T;
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;
	long double val;
	for (i=1; i<=m; i++)
		CF[i]=log10(C[i]);
	Q.push(1); var[1]=1;  
	init();
	T.insert(mp(0,1));
	while( T.size() > 0 )
	{
		val = (*T.begin()).first, x = (*T.begin()).second;
		T.erase(*T.begin());
		for (i=0; i<v[x].size(); i++)
		{
			y=v[x][i].f; z=v[x][i].s;
			if (modul(cost[y]+CF[z]-val)<=eps)
			{
				var[x]+=var[y];
				if (var[x]>=MOD)
					var[x]%=MOD;
			}
		}
		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])
			{
				var[y]=0;
				cost[y]=cost[x]+CF[z];
				T.insert(mp(cost[y],y));
			}
		}
	}
}
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;
}