#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#define Nmax 1505
#define MAX 9999999999
using namespace std;
vector<pair<int,int> >G[Nmax];
vector<pair<int,int> >::iterator it;
queue <int> C;
int n;
long long dmin[Nmax],NR[Nmax];
void reading(int &n)
{
    int k,m,x,y,z;
    freopen("dmin.in","r",stdin);
    freopen("dmin.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(k=1;k<=m;++k)
    {
        scanf("%d %d %d",&x,&y,&z);
        G[x].push_back(make_pair(y,z));
        G[y].push_back(make_pair(x,z));
    }
}
void disjktra()
{
     int i,x;
     for(i=1;i<=n;++i) {dmin[i]=MAX;NR[i]=0;}
     C.push(1);dmin[1]=0;NR[1]=1;
     while(!C.empty())
     {
         x=C.front();C.pop();
         for(it=G[x].begin();it!=G[x].end();++it)
         if (dmin[it->first]>dmin[x]+it->second)
         {
             dmin[it->first]=dmin[x]+it->second;
             C.push(it->first);
             NR[it->first]=NR[x];
         }
         else if (dmin[it->first]==dmin[x]+it->second)
         {
             NR[it->first]=NR[it->first]+NR[x];
         }
     }
}
void writte()
{
    int i;
    for(i=2;i<=n;++i) printf("%d ",NR[i]%104659);
}
int main()
{
    reading(n);
    disjktra();
    writte();
    return 0;
}