#include<vector>
#include<queue>
#include<algorithm>
#include<math.h>
using namespace std;
#define NMAX 1505
#define MOD 104659
typedef pair <int,double> p;

int n,m,i;
int x,y,z;
double zLg;

vector <p> g[NMAX];
vector <p> ::iterator it;
bool ut[NMAX];
double cost[NMAX];
int nr[NMAX];

struct cmp
{
	bool operator () (const int &i,const int &j) const
	{
		return cost[i]>cost[j];
	}
};
priority_queue <int,vector <int>,cmp> Q;

double modul(double x)
{
	if(x<0)
		return -x;
	return x;
}
void Dijkstra()
{
	for(i=1;i<=NMAX;i++)
		cost[i]=(1<<30);
	cost[1]=0;
	Q.push(1);

	while(!Q.empty())
	{
		int nod=Q.top();
		Q.pop();
		ut[nod]=0;

		for(it=g[nod].begin();it!=g[nod].end();it++)
		{
			if((cost[it->first]-cost[nod]+it->second)<=0.00000001)
				continue;

			cost[it->first]=cost[nod]+it->second;

			if(!ut[it->first])
			{
				ut[it->first]=1;
				Q.push(it->first);
			}
		}
	}
}

int main()
{
	freopen("dmin.in","r",stdin);
	freopen("dmin.out","w",stdout);

	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		zLg=logf(z);
		g[x].push_back(p(y,zLg));
		g[y].push_back(p(x,zLg));
	}

	Dijkstra();

	nr[1]=1;
	for(i=1;i<=n;i++)
		Q.push(i);
	
	while(!Q.empty())
	{
		int nod=Q.top();
		Q.pop();
		for(it=g[nod].begin();it!=g[nod].end();it++)
		{
			if(modul(cost[it->first]-cost[nod]-it->second)<=0.00000001)
				nr[it->first]=(nr[it->first]+nr[nod])%MOD;
		}
	}
	
	for(i=2;i<=n;i++)
		printf("%d ",nr[i]);

	return 0;
}