#include <stdio.h>
#include <math.h>

#define NMAX 1501
#define MMAX 2501
#define INFY 999999999.0
#define ALAS 104659
#define eps 1e-10
#define abs(a) ((a<0)?(-a):(a))

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

int main(void)
{
 // Citesc Datele
 freopen("dmin.in","r",stdin);
 freopen("dmin.out","w",stdout);
 
 scanf("%ld%ld",&n,&m);
 for (i=1;i<=m;i++)
    {
     long x,y,z;
     scanf("%ld%ld%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 1
 for (i=1;i<=n;i++)
    C[i]=0;
 for (i=1;i<=n;i++)
    C[i]=INFY; 
 C[1]=1; LUAT[1]=0; D[1]=1;
 
 // Dijsktra
 long DEX=0;
 for (DEX=1;DEX<=n;DEX++)   
    {
     double MAX=INFY;
     long 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 (abs(C[i] - (C[NOD_MAX] + (double)A[NOD_MAX][i])) > eps)
             {
              C[i] =C[NOD_MAX] + (double)A[NOD_MAX][i];
              D[i] = D[NOD_MAX] % ALAS;
             }
             else
           if (abs((C[NOD_MAX] + (double)A[NOD_MAX][i]) - C[i]) <= eps)
             {
              D[i]+=D[NOD_MAX];
              D[i]=D[i] % ALAS;
             }
          }
    } 
 
 for (i=2;i<=n;i++)
    printf("%ld ",D[i]);
    
 return 0;
}