#include <bits/stdc++.h>

using namespace std;

#define NMAX 1510
#define MOD 104659
#define EPS 0.0000000001
#define INF 1000000000


 int N,M;
 bitset < NMAX > beenThere;
 int NRD[NMAX];
 double D[NMAX];
 vector < int > A[NMAX];
 vector < double > C[NMAX];

 queue < int > myQueue;

int main()
{
    freopen("dmin.in", "r" , stdin);
    freopen("dmin.out","w", stdout);

   int a,b,nod,neighbor;

   double c , price;

   scanf("%d%d", &N , &M);

   for ( int i = 1; i <= M ; ++i)
   {
       scanf("%d%d%lf", &a,&b,&c);

       A[a].push_back(b);
       C[a].push_back(log10(c));
       A[b].push_back(a);
       C[b].push_back(log10(c));
   }

   for ( int i = 2 ; i <= N ; ++i)
    D[i] = INF;

   NRD[1] = 1;
   myQueue.push(1);
   beenThere[1] = true;

   while(!myQueue.empty())
   {
       nod = myQueue.front();
       myQueue.pop();

       beenThere[nod] = false;

       for ( size_t i = 0 ; i < A[nod].size() ; ++i)
       {
           neighbor = A[nod][i];
           price = C[nod][i];

           if( D[neighbor] > D[nod] + price + EPS)
           {
               D[neighbor] = D[nod] + price;
               NRD[neighbor] = NRD[nod]%MOD;

               if(!beenThere[neighbor])
               {
                   beenThere[neighbor] = true;
                   myQueue.push(neighbor);
               }
           }

           else if(abs(D[neighbor] - D[nod] - price) < EPS)
            NRD[neighbor] = (NRD[neighbor] %MOD + NRD[nod] %MOD) %MOD;
       }
   }

   for ( int i = 2 ; i <= N ; ++i)
    printf("%d ", NRD[i]);
}