#include <fstream>
#define eps 1e-10
#include <queue>
#include <vector>
#include <cmath>
#define mod 104659
using namespace std;
ifstream f("dmin.in");
ofstream g("dmin.out");
long double d[1502];
int n,m,i,x,y,c,j,nr[1502];
vector <pair <int,int> > v[1502];
queue <int> q;
int main()
{
    f>>n>>m;
    for (i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        v[x].push_back(make_pair(y,c));
        v[y].push_back(make_pair(x,c));
    }
    q.push(1);
    for (i=1;i<=n;i++)
        d[i]=100000;
    d[1]=0;
    nr[1]=1;
    while(!q.empty())
    {
      x=q.front();
      q.pop();
      for (j=0;j<v[x].size();j++)
        if (d[v[x][j].first]-eps>d[x]+log10l(v[x][j].second))
            nr[v[x][j].first]=nr[x],d[v[x][j].first]=d[x]+log10l(v[x][j].second),q.push(v[x][j].first);
          else if (fabs(d[v[x][j].first]-d[x]-log10l(v[x][j].second))<eps)
            nr[v[x][j].first]+=nr[x],nr[v[x][j].first]%=mod;
    }
    for (i=2;i<=n;i++)
        g<<nr[i]<<' ';
    return 0;
}