#include <stdio.h>

#define NMAX 1501
#define MMAX 2501
#define INFY 9999999
#define ALAS 104659

int i,j,n,m,A[NMAX][NMAX],C[NMAX],D[NMAX],LUAT[NMAX];

int main(void)
{
 // Citesc Datele
 freopen("dmin.in","r",stdin);
 freopen("dmin.out","w",stdout);
 
 scanf("%d%d",&n,&m);
 for (i=1;i<=m;i++)
    {
     int x,y,z;
     scanf("%d%d%d",&x,&y,&z);
     A[x][y]=z;
     A[y][x]=z;
    }
 
 // Fac toate costurile pe drumuri infinit mai putin cel de pe 1 care e 0
 for (i=1;i<=n;i++)
    C[i]=INFY;
 C[1]=1; LUAT[1]=0; D[1]=1;
 
 // Dijsktra
 int DEX=0;
 for (DEX=1;DEX<=n;DEX++)   
    {
     int MAX=INFY,NOD_MAX;
     
     // Caut nodul in care se ajunge cu drum minim
     for (i=1;i<=n;i++)
        if (C[i] < MAX && !LUAT[i])
          {
           MAX=C[i];
           NOD_MAX=i;
          }
          
     // Marchez nodul curent ca fiind luat
     LUAT[NOD_MAX] = 1;
     
     // Ma duc pe toti fii acestui nod si incerc sa expandez drumul
     for (i=1;i<=n;i++)
        if (A[NOD_MAX][i])
          {
           if (C[NOD_MAX] * A[NOD_MAX][i] < C[i])
             {
              C[i] = C[NOD_MAX] * A[NOD_MAX][i];
              D[i] = D[NOD_MAX];
             }
             else
           if (C[NOD_MAX] * A[NOD_MAX][i] == C[i])
             {
              D[i]+=D[NOD_MAX];
              D[i]=D[i] % ALAS;
             }
          }
    } 
    
 for (i=2;i<=n;i++)
    printf("%d ",D[i]);
    
 return 0;
}