#include <cstdio>
#include <cstdlib>
#include <string>
#include <cmath>

#define FIN "dmin.in"
#define FOUT "dmin.out"
#define NMAX 1501
#define INF 0x3f3f3f3f
#define PRIM 104659

int *lv[NMAX], gr[NMAX], N, M, s[NMAX], p[NMAX];
long long d[NMAX], *cost[NMAX];
double const eps = 0.00000000000001;

void read ()
{
  int x, y, c;
  
  scanf ("%d%d", &N, &M);

  for (int i = 1; i <= M; ++ i)
   {
     scanf ("%d%d%d", &x, &y, &c);
     ++ gr[x];
     ++ gr[y];
   }

  for (int i = 1; i <= N; ++ i)
   {
     lv[i] = (int *) malloc ((gr[i] + 1) * sizeof (int));
     cost[i] = (long long *) malloc ((gr[i] + 1) * sizeof (long long));
     lv[i][0] = 0;
     gr[i] = 0;
   }

  fseek (stdin, 0, SEEK_SET);

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

  for (int i = 1; i <= M; ++ i)
   {
     scanf ("%d%d%d", &x, &y, &c);
     lv[x][++lv[x][0]] = y;
     lv[y][++lv[y][0]] = x;
     cost[x][++gr[x]] = c;
     cost[y][++gr[y]] = c;
   }
}

void solve ()
{
  long long pmin, min;

  for (int i = 1; i <= N; ++ i)
    d[i] = 10000000;

  d[1] = 1;
  p[1] = 1;

  for (int k = 1; k < N; ++ k)
   {
     min = 10000000;
     for (int i = 1; i <= N; ++ i)
       if (!s[i])
         if (min > d[i])
          {
            min = d[i];
            pmin = i;
          }
          
     s[pmin] = 1;

     for (int i = 1; i <= lv[pmin][0]; ++ i)
       if (d[lv[pmin][i]] > min * cost[pmin][i])
        {
          d[lv[pmin][i]] = min * cost[pmin][i];
          p[lv[pmin][i]] = p[pmin];
        }
       else
         if (d[lv[pmin][i]] == min * cost[pmin][i])
          {
            p[lv[pmin][i]] += p[pmin];
            if (p[lv[pmin][i]] > PRIM)
              p[lv[pmin][i]] -= PRIM;
          }
   }

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

int
 main ()
{
  freopen (FIN, "rt", stdin);
  freopen (FOUT, "wt", stdout);

  read ();
  solve ();

  return 0;
}