#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<bitset>
#include<math.h>
using namespace std;
struct nod {
	int y;
	double cost;
	inline nod(int _y, double _cost) {
		y=_y;
		cost=_cost;
	}
	inline bool operator < (const nod &c) const {
		return (double)cost>c.cost;
	}
};
priority_queue <nod> c;
vector <nod> v[1501];
int pos[1501];
double d[1501];
bitset <1501> p;
void dijkstra()
{
	int x;
	c.push(nod(1,0));
	while(c.empty()==0) {
		x=c.top().y;
		c.pop();
		if(p[x]==0) {
			p[x]=1;
			for(vector <nod> :: iterator it=v[x].begin();it!=v[x].end();it++) {
				if(it->y!=1) {
				if(d[it->y]>((double)d[x]+it->cost)) {
					d[it->y]=(double)d[x]+it->cost;
					pos[it->y]=(pos[it->y]+pos[x])%104659;
					c.push(nod(it->y,d[it->y]));
				}
				else if(d[it->y]==((double)d[x]+it->cost)) {
					pos[it->y]=(pos[it->y]+pos[x])%104659;
					c.push(nod(it->y,d[it->y]));
				}
				}
			}
		}
	}
}
int main ()
{
	int i,n,m,x,y;
	double cost;
	ifstream f("dmin.in");
	ofstream g("dmin.out");
	f>>n>>m;
	for(i=1;i<=m;i++) {
		f>>x>>y>>cost;
		cost=log(cost);
		v[x].push_back(nod(y,cost));
		v[y].push_back(nod(x,cost));
	}
	f.close();
	for(i=1;i<=n;i++)
		d[i]=2147000000;
	d[1]=1;
	pos[1]=1;
	dijkstra();
	for(i=2;i<=n;i++)
		g<<pos[i]%104659<<" ";
	g.close();
	return 0;
}