#include <fstream>
#include <vector>
#include <cmath>

using namespace std;

const char InFile[]="dmin.in";
const char OutFile[]="dmin.out";
const int MaxN=1500;
const int MOD=104659;
const double INF=1.0e64;
const double EPS=1.0e-10;

ifstream fin(InFile);
ofstream fout(OutFile);

struct s_edge
{
	s_edge(int to, double cost):to(to),cost(cost){}
	int to;
	double cost;
};

int N,M,x,y,sol[MaxN],viz[MaxN];
double cost,D[MaxN];
vector<s_edge> G[MaxN];

inline bool d_equal(double a, double b)
{
	return fabs(a-b)<=EPS;
}

int main()
{
	fin>>N>>M;
	for(register int i=1;i<=M;++i)
	{
		fin>>x>>y>>cost;
		cost=log(cost);
		G[x].push_back(s_edge(y,cost));
		G[y].push_back(s_edge(x,cost));
	}
	fin.close();
	
	sol[1]=1;
	for(register int i=2;i<=N;++i)
	{
		D[i]=INF;
	}
	
	for(register int i=1;i<=N;++i)
	{
		int bestnod=0;
		double bestcost=INF;
		for(register int j=1;j<=N;++j)
		{
			if(D[j]<bestcost && !viz[j])
			{
				bestcost=D[j];
				bestnod=j;
			}
		}
		
		viz[bestnod]=1;
		for(vector<s_edge>::iterator it=G[bestnod].begin();it!=G[bestnod].end();++it)
		{
			if(d_equal(D[it->to],D[bestnod]+it->cost))
			{
				sol[it->to]+=sol[bestnod];
				if(sol[it->to]>=MOD)
				{
					sol[it->to]-=MOD;
				}
			}
			else if(D[it->to]>D[bestnod]+it->cost)
			{
				D[it->to]=D[bestnod]+it->cost;
				sol[it->to]=sol[bestnod];
			}
		}
	}
	
	for(register int i=2;i<=N;++i)
	{
		fout<<sol[i]<<" ";
	}
	fout.close();
	return 0;
}