#include<fstream>
#include<cmath>
#include<vector>
#include<queue>
#define dmax 1520
#define inf 999999
#define EPS 1e-9
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;
		}
	  
	  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;
}