#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<deque>
#include<climits>
#define mod 104659
#define E 1e-9
using namespace std;

int n,i,j,k,rez[1501],m,x,y;
double cost,dist[1501];
bool viz[1501];
deque<int>c;
vector<pair<int,double> > v[1501];

int main()
{
	freopen("dmin.in","r",stdin);
	freopen("dmin.out","w",stdout);
	scanf("%d %d",&n,&m);
	for (i=1;i<=n;i++)
	{
		scanf("%d %d %d",&x,&y,&k);
		cost=log(k);
		v[x].push_back(make_pair(y,cost));
		v[y].push_back(make_pair(x,cost));
	}
	c.push_back(1);
	fill(dist+1,dist+n+1,9999999.0);
	rez[1]=1;
	dist[1]=0;
	viz[1]=true;
	while (!c.empty())
	{
		x=c.front();
		c.pop_front();
		viz[x]=false;
		for (j=0;j<v[x].size();j++)
		{
			y=v[x][j].first;
			cost=v[x][j].second;
			if (dist[x]+cost+E<dist[y])
					{
					dist[y]=dist[x]+cost;
					rez[y]=rez[x];
					if (rez[y]>mod) rez[y]-=mod;
					if (!viz[y]) viz[y]=true,c.push_back(y);
				}else
			if (fabs(dist[x]+cost-dist[y])<E)
				{
					rez[y]=rez[x]+rez[y];
					if (rez[y]>mod) rez[y]-=mod;
			}
		}		
	}
	for (i=2;i<=n;i++)
		printf("%d ",rez[i]);
	return 0;
}