#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#define LMAX 1505
#define INF 999999999
#define EPS 1e-6

using namespace std;
FILE *fin=fopen("dmin.in","r");
FILE *fout=fopen("dmin.out","w");

struct muchie {
    int x;
    float c;
};

vector <muchie> vec[LMAX];

int n, m;

queue <int> Q;

float dmin[LMAX];
int nrd[LMAX];

void citire();
void calculare();
void afisare();

int main()
{
citire();
calculare();
afisare();
fclose(fin);
fclose(fout);
return 0;
}

void calculare()
    {
     int act;
     int vecin;
     double cost;
     unsigned int i;
     for (i=2;i<=n;i++)
          dmin[i]=INF;
     nrd[1]=1;
     Q.push(1);
     while (!Q.empty())
         {
          act=Q.front();
          Q.pop();
          for (i=0;i<vec[act].size();i++)
             {
              vecin=vec[act][i].x;
              cost=vec[act][i].c;
              if (dmin[vecin]>(dmin[act]+cost))
                 {
                  dmin[vecin]=dmin[act]+cost;
                  nrd[vecin]=nrd[act];
                  Q.push(vecin);
                 }
                 else
                 if (abs(dmin[vecin]-(dmin[act]+cost))<EPS)
                     {nrd[vecin]+=nrd[act];}
             }
         }
    }

void afisare()
    {
     int i;
     for (i=2;i<=n;i++)
          fprintf(fout,"%d ",nrd[i]%104659);
     fprintf(fout,"\n");
    }

void citire()
    {
     int i;
     int x, y, c;
     muchie a;
     fscanf(fin,"%d %d",&n,&m);
     for (i=1;i<=m;i++)
         {
          fscanf(fin,"%d %d %d",&x,&y,&c);
          a.x=x;
          a.c=log(c);
          vec[y].push_back(a);
          a.x=y;
          a.c=log(c);
          vec[x].push_back(a);
         }
    }