#include <fstream>
#include <cmath>
#include <vector>
#include <algorithm>
#define EPS 0.000001
#define MOD 104659
using namespace std;
int n,m,nr[1510];
struct Muchie{int x,y;double cost;};
Muchie M[2510];
vector <int> G[1510], Q;
double dist[1510];
bool viz[1510];

void Citire()
{
	int i;
	ifstream fin("dmin.in");
	fin>>n>>m;
	for(i=1;i<=m;i++)
	{
		fin>>M[i].x>>M[i].y>>M[i].cost;
		M[i].cost=log(M[i].cost);
		G[M[i].x].push_back(i);
		G[M[i].y].push_back(i);
	}
	fin.close();
}

bool Sortare(int a, int b)
{
	return dist[a] > dist[b];
}

void Bellman_Ford()
{
	vector <int>::iterator it;
	int i,x,y;
	for(i=2;i<=n;i++)
		dist[i]=2000000000.0;
	nr[1]=1;
	viz[1]=true;
	Q.push_back(1);
	while(Q.size())
	{
		x=Q[0];
		pop_heap(Q.begin(), Q.end(), Sortare);
		Q.pop_back();
		viz[x]=false;
		for(it=G[x].begin();it!=G[x].end();it++)
		{
			y=M[*it].x+M[*it].y-x;
			if(EPS<dist[y]-dist[x]-M[*it].cost)
			{
				dist[y]=dist[x]+M[*it].cost;
				nr[y]=nr[x];
				if(!viz[y])
				{
					viz[y]=true;
					Q.push_back(y);
					push_heap(Q.begin(), Q.end(), Sortare);
				}
			}
			else
				if(dist[x]+M[*it].cost-dist[y]<=EPS)
				{
					nr[y]+=nr[x];
					if(nr[y]>=MOD)
						nr[y]-=MOD;
				}
		}
	}
}

void Afisare()
{
	int i;
	ofstream fout("dmin.out");
	for(i=2;i<=n;i++)
		fout<<nr[i]<<' ';
	fout<<"\n";
	fout.close();
}

int main()
{
	Citire();
	Bellman_Ford();
	Afisare();
	return 0;
}