#include<fstream>
#include<vector>
#include<queue>
using namespace std;
#define mod %104659
ifstream f("dmin.in");
ofstream g("dmin.out");
struct pairr { int to,cost; };
pairr mp(int x,int y) 
{	pairr c; c.to=x , c.cost=y; 
	return c; 
}
vector<pairr>a[1501];
int cmin[1501],way[1501];
queue<int>q;
void BFS()
{	int i,k,j,co;
	q.push(1);
	cmin[1]=1; 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(cmin[j]==0)
				cmin[j]=((cmin[i] mod)*(co mod))mod , way[j]=way[i] , q.push(j);
			else
				if(cmin[j]>((cmin[i] mod)*(co mod))mod)
					cmin[j]=((cmin[i] mod) * (co mod))mod , way[j]=(way[j]mod +way[i]mod)mod , q.push(j);
				else if(cmin[j]==((cmin[i] mod)* (co mod))mod) way[j]=(way[j]mod +way[i]mod)mod;
		}
	}
}
int main()
{	int i,j,x,y,c,N,M;
	f>>N>>M;
	for(i=1;i<=M;i++)
	{	f>>x>>y>>c;
		a[x].push_back(mp(y,c));
		a[y].push_back(mp(x,c));
	}
	BFS();
	for(i=2;i<=N;i++)
		g<<way[i]<<" ";
	f.close();
	g.close();
	return 0;
}