#include<cstdio>
#include<vector>
#include<cmath>
#define baz 0.00000001
#define db 104659
using namespace std;
const int N=2501,M=1000001;
int q[M],p,u,nr[N],s[N],n,m;
double c[N];
bool viz[N];
struct xy{
	int to;
	double c;
};
vector <xy> v[N];

void read()
{
	int x,y,z;
	xy a;
	scanf("%d%d",&n,&m);
	for( int i=1 ; i<=m ; ++i )
	{
		scanf("%d%d%d",&x,&y,&z);
		a.to=y;
		a.c=log10((double)z);
		v[x].push_back(a);
		s[x]++;
		a.to=x;
		v[y].push_back(a);
		s[y]++;
	}
}

void check(int x)
{
	for( int i=0 ; i<s[x] ; ++i )
		if( c[v[x][i].to]-(c[x]+v[x][i].c)>baz || viz[v[x][i].to]==0 )
		{
			q[++u]=v[x][i].to;
			nr[v[x][i].to]=nr[x]%db;
			c[v[x][i].to]=c[x]+v[x][i].c;
			viz[v[x][i].to]=1;
		}
		else if( c[v[x][i].to] - ( c[x] + v[x][i].c) < baz && c[v[x][i].to] - (c[x]+v[x][i].c)>-baz)
			nr[v[x][i].to]=(nr[v[x][i].to]+nr[x])%db;
}

void solve()
{
	p=1;
	u=1;
	q[1]=1;
	viz[1]=1;
	nr[1]=1;
	while(p<=u)
	{
		check(q[p]);
		++p;
	}
}

void print()
{
	for( int i=2 ;i<=n; ++i )
		printf("%d ",nr[i]);
}

int main()
{
	freopen("dmin.in","r",stdin);
	freopen("dmin.out","w",stdout);
	read();
	solve();
	print();
	return 0;
}