#include <fstream>
#include <set>
#include <vector>
#include <cmath>
#define MP make_pair
#define st first
#define nd second
#define eps 1e-9

using namespace std;

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

const int MOD = 104659;
const double INF = 160000000;
vector< pair<int,double > > G[1502];
int N , M , drumuri[1502];
double D[1502];

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(fabs(D[w->st] - v.st - w->nd) < eps)
				drumuri[w->st]= (drumuri[w->st] + drumuri[v.nd])%MOD;
			else
		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));
		}
	}
}

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

}

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