#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#define LMAX 1505
#define INF 999999999
#define EPS 0.0000000001
#define MOD 104659

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

struct muchie {
    int x;
    double c;
};

vector <muchie> vec[LMAX];

int n, m;

bool uz[LMAX];

queue <int> Q;

double 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;
     uz[1]=1;
     Q.push(1);
     while (!Q.empty())
         {
          act=Q.front();
          uz[act]=0;
          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+EPS))
                 {
                  dmin[vecin]=dmin[act]+cost;
                  nrd[vecin]=nrd[act]%MOD;
                  if (!uz[vecin])
                      {uz[vecin]=1;
                      Q.push(vecin);}
                 }
                 else
                 if (abs(dmin[vecin]-dmin[act]-cost)<EPS)
                     {nrd[vecin]=(nrd[vecin] + nrd[act])%MOD;}
             }
         }
    }

void afisare()
    {
     int i;
     for (i=2;i<=n;i++)
          fprintf(fout,"%d ",nrd[i]%MOD);
     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=log10(c);
          vec[y].push_back(a);
          a.x=y;
          a.c=log10(c);
          vec[x].push_back(a);
         }
    }