#include <bits/stdc++.h>
#define NMAX 1502
#define INF 1000001
#define eps 1e-8
#define MOD 104659
using namespace std;
ifstream f("dmin.in"); ofstream g("dmin.out");
inline double modul(double x)
{   if(x<0) return -x;
    return x;
}
vector < pair < int,double > >G[NMAX];
queue <int> Q;
int n, m, nrd[NMAX];
double dmin[NMAX];
bool viz[NMAX];
void bellmanFord()
{   int x, vecin;
    double cost;
    Q.push(1);
    viz[1]=1;
    while (!Q.empty())
    {   x=Q.front();
        Q.pop();
        for (int i=0;i<G[x].size();i++)
        {   vecin=G[x][i].first;
            cost=G[x][i].second;
            if(dmin[vecin]-eps>dmin[x]+cost)
            {   dmin[vecin]=dmin[x]+cost;
                nrd[vecin]=nrd[x];
                if(!viz[vecin])
                {   Q.push(vecin); viz[vecin]=1; }
            }
            else if(modul(dmin[vecin]-dmin[x]-cost)<=eps) nrd[vecin]=(nrd[vecin]+nrd[x])%MOD;
        }
    }
}
int main()
{   double z,cost;
    f>>n>>m;
    for (int x,y,i=1;i<=m;i++)
    {   f>>x>>y>>cost;
        z=log(cost);
        G[x].push_back(make_pair(y,z));
        G[y].push_back(make_pair(x,z));
    }
    nrd[1]=1;
    for (int i=2;i<=n;i++) dmin[i]=INF;
    bellmanFord();
    for(int i=2;i<=n;++i) g<<nrd[i]<<' ';
    return 0;
}