#include<cstdio>
#include<vector>
#include<queue>
#define NMAX 1505
#define INF (1<<30)
#define US unsigned short
#define DIJKSTRA_TYPE pair<US,US> 
#define MOD 104659
using namespace std;
FILE *fin,*fout;
vector < pair<US,US> > G[NMAX];
int n,d[NMAX],k,apar[NMAX];
priority_queue< DIJKSTRA_TYPE, vector<DIJKSTRA_TYPE>, greater<DIJKSTRA_TYPE> > HEAP;
bool use[NMAX];
void dijkstra(US nod)
{
	US vec,cost;
	for(int i=1;i<=n;i++)
		d[i]=INF;
	d[nod]=1;
	HEAP.push(make_pair(1,nod));
	while(!HEAP.empty())
	{
		nod=HEAP.top().second;
		if(use[nod])
		{
			if(d[nod]==HEAP.top().first)
				apar[nod]++;
		}
		else
		{
			apar[nod]=1;
			use[nod]=1;
		}
		HEAP.pop();
		for(size_t i=0;i<G[nod].size();i++)
		{
			vec=G[nod][i].first;
			cost=G[nod][i].second;
			if(d[vec]>=d[nod]*cost)
			{
				d[vec]=d[nod]*cost;
				HEAP.push(make_pair(d[vec],vec));
			}
		}
	}
}
void read()
{
	fin=fopen("dmin.in","r");
	int x,y,z,m;
	fscanf(fin,"%d %d",&n,&m);
	while(m--)
	{
		fscanf(fin,"%d %d %d",&x,&y,&z);
		G[x].push_back(make_pair(y,z));
		G[y].push_back(make_pair(x,z));
	}
	fclose(fin);
}
void print()
{
	fout=fopen("dmin.out","w");
	for(int i=2;i<=n;i++)
		fprintf(fout,"%d ",apar[i]%MOD);
	fclose(fout);
}
int main()
{
	read();
	dijkstra(1);
	print();
	return 0;
}