#include <cstdio>
#include <cmath>
#include <iterator>
#include <list>
#define INF "dmin.in"
#define OUF "dmin.out"
#define NMAX 2048
#define EPS 0.01
#define CLB 104659

using namespace std;
int fv[NMAX]={0},friz[NMAX]={0},n,m;
double cost[NMAX];
struct nod
{
	int x;
	double cost;
}op;
list<nod> lt[NMAX];
list<int> que;
void road()
{
     list<int>::iterator it,min;
     list<nod>::iterator nd;
     double mini,w;
     int pt;
     while(!que.empty())
     {
	     mini=(1<<25);
	     for(it=que.begin();it!=que.end();it++)
		     if(cost[(*it)]<mini) {mini=cost[(*it)];min=it;}
	     pt=(*min);que.erase(min);mini=cost[pt];friz[pt]=1;
	     //printf("%d ",pt);
	     for(nd=lt[pt].begin();nd!=lt[pt].end();nd++)
	     if(!friz[nd->x])
	     {
	             w=cost[nd->x]-(mini+(nd->cost));
		     if(w>=0&&w<EPS) fv[nd->x]=(fv[pt]+fv[nd->x])%CLB;
		     else if(w>0)  
		     {
			     cost[nd->x]=mini+(nd->cost);
			     fv[nd->x]=fv[pt];
		     }
	     }
     }
}

int main()
{
      FILE *in,*out;
      in=fopen(INF,"r");
      out=fopen(OUF,"w");
      int i,a,b;
      double c;
      fscanf(in,"%d %d",&n,&m);
      for(i=1;i<=m;i++)
      {
	      fscanf(in,"%d %d %lf",&a,&b,&c);
	      op.x=b;op.cost=log(c);
	      lt[a].push_back(op);
	      op.x=a;
	      lt[b].push_back(op);
      }
      cost[1]=1;que.push_back(1);fv[1]=1;
      for(i=2;i<=n;i++) {que.push_back(i);cost[i]=(1<<24);}
      road();
      for(i=2;i<=n;i++) fprintf(out,"%d ",fv[i]);
      fclose(in);fclose(out);
      return 0;
}