#include<fstream>
#include<vector>
#include<queue>
#include<math.h>
using namespace std;
#define mod %104659
#define eps 1e-10
ifstream f("dmin.in");
ofstream g("dmin.out");
struct pairr { int to; double cost; };
double abss(double x) { return x<0?-1*x:x; }
pairr mp(int x,double y) 
{	pairr c; c.to=x , c.cost=y; 
	return c; 
}
vector<pairr>a[1501];
double cmin[1501];
int way[1501];
queue<int>q;
void BFS()
{	int i,k,j; double co; 
	q.push(1);
	cmin[1]=0; way[1]=1;
	while(!q.empty())
	{	i=q.front(); q.pop();
		for(k=0;k<a[i].size();k++)
		{	j=a[i][k].to , co=a[i][k].cost;
			if(j==1) continue;
			if(cmin[j]==-1)
				cmin[j]=cmin[i]+co , way[j]=way[i] , q.push(j);
			else
				if(cmin[j]>cmin[i]+co)
					cmin[j]=cmin[i]+co , way[j]=(way[j]mod +way[i]mod)mod , q.push(j);
				else if(abss(cmin[j]-(cmin[i]+co))<=eps) 
					way[j]=(way[j]mod +way[i]mod)mod;
		}
	}
}
int main()
{	int i,j,x,y,N,M; double c;
	f>>N>>M;
	for(i=1;i<=M;i++)
	{	f>>x>>y>>c;
		a[x].push_back(mp(y,log(c)));
		a[y].push_back(mp(x,log(c)));
	}
	for(i=1;i<=N;i++) cmin[i]=-1;
	BFS();
	for(i=2;i<=N;i++)
		g<<way[i]<<" ";
	f.close();
	g.close();
	return 0;
}