//Ilie Dumitru
#include<cstdio>
#include<cmath>
#include<queue>
#include<vector>
const int NMAX=1505;
const int MOD=104659;
const double EPS=1e-6;

struct pos
{
	int node;
	double dist;

	friend bool operator<(pos a, pos b)
	{
		return a.dist>b.dist;
	}
};

int N;
double minDist[NMAX];
int nrMin[NMAX];
std::priority_queue<pos> pq;
std::vector<pos> G[NMAX];

void dijkstra()
{
	pos a, b;
	int i;

	for(i=1;i<N;++i)
		minDist[i]=NMAX*1000;

	nrMin[0]=1;
	a.node=0;
	a.dist=0;
	pq.push(a);

	do
	{
		a=pq.top();
		pq.pop();

		if(a.dist==minDist[a.node])
		{
			for(i=0;i<(int)G[a.node].size();++i)
			{
				b.node=G[a.node][i].node;
				b.dist=a.dist+G[a.node][i].dist;
				if(fabs(b.dist-minDist[b.node])<EPS)
					nrMin[b.node]=(nrMin[b.node]+nrMin[a.node])%MOD;
				else if(b.dist<minDist[b.node])
				{
					minDist[b.node]=b.dist;
					nrMin[b.node]=nrMin[a.node];
					pq.push(b);
				}
			}
		}
	}while(!pq.empty());
}

int main()
{
	FILE* f=fopen("dmin.in", "r"), *g=fopen("dmin.out", "w");
	int i, M, a, b, c;
	double aux;

	fscanf(f, "%d%d", &N, &M);
	for(i=0;i<M;++i)
	{
		fscanf(f, "%d%d%d", &a, &b, &c);
		aux=log(c);
		G[--a].push_back({--b, aux});
		G[b].push_back({a, aux});
	}

	dijkstra();
	for(i=1;i<N;++i)
		fprintf(g, "%d ", nrMin[i]);

	fclose(f);
	fclose(g);
	return 0;
}