#include<fstream>
#include<vector>
#include<queue>
#include<math.h>
using namespace std;
#define mod %104659
#define eps 1e-10
#define inf 1000000000
ifstream f("dmin.in");
ofstream g("dmin.out");
struct pairr { int to; float cost; };
pairr mp(int x,float y) 
{	pairr c; c.to=x , c.cost=y; 
	return c; 
}
vector<pairr>a[1501];
float cmin[1501];
bool v[1501];
int way[1501];
queue<int>q;
void BFS()
{	int i,k,j; float co; 
	q.push(1);
	cmin[1]=0; way[1]=1;
	while(!q.empty())
	{	i=q.front(); q.pop(); v[i]=false;
		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]>cmin[i]+co)
			{	cmin[j]=cmin[i]+co;
				way[j]=way[i];
				if(v[j]==false)
				{	q.push(j);
					v[j]=true;
				}
			}else if(abs(cmin[j]-cmin[i]-co)<eps)
					way[j]=(way[j]mod+way[i]mod)mod;
		}
	}
}
int main()
{	int i,j,x,y,N,M; float 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]=inf;
	BFS();
	for(i=2;i<=N;i++)
		g<<way[i]<<" ";
	f.close();
	g.close();
	return 0;
}