#include<fstream>
#include<cmath>
#include<vector>
#include<queue>

#define dmax 1520
#define inf 999999
#define EPS 1e-12
using namespace std;

int n,m;
double d[dmax];
int nrdr[dmax];
bool v[dmax];

vector<int> a[dmax], c[dmax];
queue<int> q;

void citire()
{
 int i,x,y,z;
 
 ifstream fin("dmin.in");
 fin>>n>>m;
 for (i=1; i<=m; i++)
	 {
	  fin>>x>>y>>z;
	  a[x].push_back(y); c[x].push_back(z);
	  a[y].push_back(x); c[y].push_back(z);
	 }
 
 fin.close();
}


void solve()
{
 int i,elem;
 double logc;
 
 d[1]=1;
 for (i=2; i<=n; i++)
	 d[i]=inf;
 nrdr[1]=1;
 
 q.push(1); 
 
 while (q.size())
	 {
	  elem=q.front();  
	  
	  for (i=0; i<a[elem].size(); i++)
		  {
		   logc=log(double(c[elem][i]));
		   
		   if (d[a[elem][i]] - (d[elem] + logc) > EPS)
		     {
			   d[a[elem][i]] = d[elem] + logc;
			   nrdr[a[elem][i]] = (nrdr[elem] % 104659);
			   if (v[a[elem][i]] == false)
				   {
				    q.push(a[elem][i]);
					v[a[elem][i]]=true;
				   }
			  } else
			  if (abs(d[a[elem][i]] - (d[elem] + logc)) < EPS)
				 nrdr[a[elem][i]] = ( (nrdr[a[elem][i]] % 104659) + (nrdr[elem] % 104659) ) % 104659;
		 
		   /*if (d[a[elem][i]] > d[elem] * c[elem][i])
		     {
			   d[a[elem][i]] = d[elem] * c[elem][i];
			   nrdr[a[elem][i]] = (nrdr[elem] % 104659);
			   if (v[a[elem][i]] == false)
				   {
				    q.push(a[elem][i]);
					v[a[elem][i]]=true;
				   }
			  } else
			  if (d[a[elem][i]] == d[elem] * c[elem][i])
				 nrdr[a[elem][i]] = ( (nrdr[a[elem][i]] % 104659) + (nrdr[elem] % 104659) ) % 104659;*/
		  }
	  
	  q.pop(); v[elem]=false;
	 }
}


void afisare()
{
 int i;
	
 ofstream fout("dmin.out");
 for (i=2; i<=n; i++)
	 fout<<nrdr[i]<<" ";
 
 fout.close();
}

int main()
{
	
 citire();
 solve();
 afisare();
	
 return 0;
}