#include<cstdio>
#include<queue>
#include<vector>
#include<cstring>
#include<utility>
#include<bitset>
#include<cmath>

#define INF 0x3f3f3f3f
#define NMAX 50005
#define PREC 0.000001
#define MOD 104659
#define TYPE pair<int,int>

FILE *f=fopen("dmin.in","r");
FILE *g=fopen("dmin.out","w");

using namespace std;

vector<pair <int,int> >G[NMAX];
vector<int>::iterator it;
int n,m,dist[NMAX],res[NMAX];
priority_queue<TYPE,vector<TYPE>,greater<TYPE> > HEAP;
bool used[NMAX];

void read( void )
{
    fscanf(f,"%d%d",&n,&m);

    for(int i(1); i <=m ; ++i )
    {
        int a,b,c;
        fscanf(f,"%d%d%d",&a,&b,&c);
        G[a].push_back(make_pair(b,c));
        G[b].push_back(make_pair(a,c));
    }
    fclose(f);

}
void DIJKSTRA( void )
{
    for(int i(1); i<=n ; dist[i++]=INF);

  dist[1]=0;
  res[1]=1;
  HEAP.push(make_pair(0,1));

  while(!HEAP.empty())
  {
      int node=HEAP.top().second;
      HEAP.pop();
     if( used[node])
        continue;
     used[node]=1;

      for(int i(0); i <G[node].size(); ++i )
      {
       int newnode=G[node][i].first;
       int dis=G[node][i].second;

       if( dist[newnode] > dist[node]+dis)
          {
              dist[newnode]=dist[node]+dis;
                res[newnode]=res[node];
              HEAP.push(make_pair(dist[newnode],newnode));
			  continue;
          }

        if(dist[newnode] == (dist[node]+dis ))
        {
            res[newnode]+=res[node];
            res[newnode]%=MOD;
			continue;
        }

      }

  }


}
void write( void )
{
    for(int i(2); i <=n; ++i )

        fprintf(g,"%d ",res[i]);

    fclose(g);
}


int main( void )
{
    read();
    DIJKSTRA();
    write();
    return 0;
}