#include <fstream>
#include <set>
#include <vector>
#include <cmath>
#define MP make_pair
#define st first
#define nd second

using namespace std;

ifstream fin("dmin.in");
ofstream fout("dmin.out");

const int MOD = 104659;
const double INF = double(2e9) , eps = 0.00000001;
vector< pair<int,double > > G[1502];
int N , M , drumuri[1502];
double D[1502];

static inline double absd(double x)
{
	return x > 0 ? x : -x;
}

void djikstra()
{
	for(int i=1;i<=N;++i) D[i] = INF;
	D[1] = 0;
	drumuri[1] = 1;
	set<pair<double,int> > h;
	pair<double,int> v;
	h.insert(MP(0,1));
	while(!h.empty())
	{
		v = (*h.begin()) , h.erase(*h.begin());
		for(vector<pair<int,double > >::const_iterator w = G[v.nd].begin();w!=G[v.nd].end();++w)
		if(D[w->st] > v.st + w->nd)
		{
			D[w->st] = v.st + w->nd;
			drumuri[w->st] = drumuri[v.nd];
			h.insert(MP(D[w->st],w->st));
		}
		else
			if(absd(D[w->st] -(v.st+ w->nd))<eps)
				drumuri[w->st]= (drumuri[w->st] + drumuri[v.nd])%MOD;
	}
}

void read_data()
{
	int x , y;double c;
	for(fin>>N>>M;M;M--)
	{
		fin>>x>>y>>c;
		c = log(c);
		G[x].push_back(MP(y,c));
		G[y].push_back(MP(x,c));
	}

}

int main()
{
	read_data();
	djikstra();
	for(int i=2;i<=N;++i)
		fout<<drumuri[i]<<" ";
	return 0;
}