#include<cstdio>
#include<cstring>
#include<vector>
#include<deque>
#include<bitset>
#define ll long long
#define MOD 104659
using namespace std;
vector<pair<int,int> >V[1510];
deque<int> Q;
bitset<1510> in_q;
void read(),solve();
int n,m,a,b,c,NR[1510],X,i;
ll cost[1510];
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("dmin.in","r",stdin);
	freopen("dmin.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(;m;--m)
	{
		scanf("%d%d%d",&a,&b,&c);
		V[a].push_back(make_pair(b,c));
		V[b].push_back(make_pair(a,c));
	}
}
void solve()
{
	Q.push_back(1);
	memset(cost,555,sizeof(cost));
	cost[1]=1;
	in_q[1]=1;
	NR[1]=1;
	for(;!Q.empty();)
	{
		X=Q.front();
		for(vector<pair<int,int> >::iterator it=V[X].begin();it!=V[X].end();it++)
		{
			b=it->first;
			c=it->second;
			if(cost[X]*c==cost[b])
			{
				NR[b]+=NR[X];
				if(NR[b]>MOD)NR[b]-=MOD;
				if(!in_q[b])
				{
					Q.push_back(b);
					in_q[b]=1;
				}
			}
			if(cost[X]*c<cost[b])
			{
				cost[b]=cost[X]*c;
				NR[b]=NR[X];
				if(!in_q[b])
				{
					Q.push_back(b);
					in_q[b]=1;
				}
			}
		}
		in_q[X]=0;
		Q.pop_front();
	}
	for(i=2;i<=n;i++)printf("%d ",NR[i]);
}