#include<fstream>
#define EPS 0.0000000001
#include<cmath>
using namespace std;
int n,m,vizitat[1505],drum[1505],poz[1505],h[1505],nh;
double d[1505];
struct nod{
       int info;
       double energie;
       nod *next;};
nod *g[1505];
void cerne(int k);
void adauga(int a,int b,double c);
void dijkstra();
void init();
void promoveaza(int k);
int main()
{
    ifstream fin("dmin.in");
    ofstream fout("dmin.out");
    fin>>n>>m;
    int i;
    for(i=1;i<=n;i++)
    {
      int a,b;
      double c;
      fin>>a>>b>>c;
      c=log(c);
      adauga(a,b,c);
      adauga(b,a,c);
    }
   dijkstra();
  for(i=1;i<=n;i++)
    fout<<drum[i]<<" ";
  return 0;
}
void adauga(int a,int b,double c)
{
   nod *p;
   p=new nod;
   p->info=b;
   p->energie=c;
   p->next=g[a];
   g[a]=p;
}
void dijkstra()
{
  init();
  int kkt,pmin;
  for(kkt=1;kkt<n;kkt++)
  {
    pmin=h[1];
    if(d[pmin]==1000000000)
      break;
    vizitat[pmin]=1;
    h[1]=h[nh--];
    poz[h[1]]=1;
    cerne(1);
    for(nod *p=g[pmin];p;p=p->next)
    {
     if(vizitat[p->info]==0) 
      if(d[p->info]>d[pmin]+p->energie+EPS)
        { 
         d[p->info]=d[pmin]+p->energie,drum[p->info]=drum[pmin];
          promoveaza(poz[p->info]);
         }
      else
      if (p->energie+d[pmin]-d[p->info]<EPS && p->energie+d[pmin]-d[p->info]>-EPS)
             drum[p->info]=(drum[pmin]+drum[p->info]) % 104659;
      }    
   }        
}
void init()
{
   int i;
   for(i=1;i<=n;i++)
   vizitat[i]=0,d[i]=1000000000,drum[i]=0,h[i]=i,poz[i]=i;
   nh=n;
   d[1]=0;
   vizitat[1]=1;
   h[1]=h[nh--];
   drum[1]=1;
   poz[h[1]]=1;
   cerne(1);
   for(nod *p=g[1];p;p=p->next)
    {
      d[p->info]=p->energie;
      promoveaza(poz[p->info]);
      drum[p->info]=1;    
     }
}
void promoveaza(int k)
{
   int esteheap=0,i;
   while(k/2>0 && esteheap==0)
   {
     i=k/2;
     if(d[h[k]]>=d[h[i]])
        esteheap=1;
     else
      {
        int aux;
        aux=h[i],h[i]=h[k],h[k]=aux;
        poz[h[k]]=k;poz[h[i]]=i;
        k=i;
      }
   }
}                                        
void cerne(int k)
{
   int esteheap=0,i,aux;
   while(2*k<=nh && esteheap==0)
   {
     i=2*k;
     if(i+1<=nh && d[h[i]]>d[h[i+1]])
       i=i+1;
     if(d[h[i]]>=d[h[k]])
       esteheap=1;
     else
      {
       aux=h[i],h[i]=h[k],h[k]=aux;
        poz[h[k]]=k;poz[h[i]]=i;
        k=i;
       }
    }
}