#include <cstdio>
#include <cassert>
#include <cmath>
#define Nmax 1505
#define Mod 104659
#define eps 1e-10
#define INF 10e9
#define InFile "dmin.in"
#define OutFile "dmin.out"

using namespace std;

int n, m;
int viz[Nmax], cnt[Nmax];
double C[Nmax][Nmax], d[Nmax];

void read();
void Dijkstra();
void afisare();
int compare (double, double);
void write();

int main()
{
  assert (freopen (InFile, "r", stdin));
  assert (freopen (OutFile, "w", stdout));
  read();
  Dijkstra();
  write();
  return 0;
}

void read()
{
  int i, j, x, y;
  double c;
  scanf ("%d %d\n", &n, &m);
  for (i=1; i<=n; i++) for (j=1; j<=n; j++) C[i][j]=INF;
  for (i=0; i<m; i++)
  {
    scanf ("%d %d %lf\n", &x, &y, &c);
    C[x][y]=C[y][x]=log (c);
  }
}

void Dijkstra()
{
  int i, k, ok=1, cmp;
  double Min;
  for (i=1; i<=n; i++)
    d[i]=INF;
  for (i=1; i<=n; i++)
  {
    d[i]=C[1][i];
    if (C[1][i]!=INF)
      cnt[i]=1;
  }
  viz[1]=1; ok=1;
  while (ok)
  {
    //selectez mininu
    Min=INF;
    for (i=1; i<=n; i++)
      if (!viz[i] && compare (d[i], Min)==1)
        Min=d[i], k=i;
    if (compare (Min, INF))
    {
      viz[k]=1;
      for (i=1; i<=n; i++)
      {
        cmp=compare (d[i], d[k]+C[k][i]);
        if (!viz[i] && cmp==-1)//if (d[i]>d[k]+C[k][i])
        {
          d[i]=d[k]+C[k][i];
          cnt[i]=cnt[k];
        }
        else
          if (!cmp)//if (d[i]==d[k]+C[k][i])
            cnt[i]=(cnt[i]+cnt[k])%Mod;
      }
    }
    else ok=0;
  }
}

int compare(double a, double b)
{
  if (a+eps<b)
    return 1;
  if (b+eps<a)
    return -1;
  return 0;
}

void write()
{
  int i;
  for (i=2; i<=n; i++)
    printf ("%d ", cnt[i]);
  printf ("\n");
}