#include <fstream>
#include <cmath>
#include <vector>
#define INF 100000
#define MOD 104659
using namespace std;
ifstream f("dmin.in");
ofstream g("dmin.out");
int N,M;
int Use[1505],Heap[1505],Poz[1505],NHeap;
double D[1505];
int Result[1505];
const double eps=0.000001;
vector < pair <int,double> > G[1505];
void Read()
{
    int i;
    f>>N>>M;
    for(int i=1;i<=M;i++)
    {
        int x,y;
        double cost;
        f>>x>>y>>cost;
        cost=log(cost);
        G[x].push_back(make_pair(y,cost));
        G[y].push_back(make_pair(x,cost));
    }
    for(i=2;i<=N;i++)
        D[i]=INF;
}

void Swap(int X, int Y)
{
    swap(Heap[X],Heap[Y]);
    swap(Poz[Heap[X]],Poz[Heap[Y]]);
}
void Sift(int X)
{
    int Son=(X<<1);
    if(Son+1<=NHeap && D[Heap[Son+1]]<D[Heap[Son]])
      Son++;
    if(Son<=NHeap && D[Heap[Son]]<D[Heap[X]])
        {
            Swap(Son,X);
            Sift(Son);
        }
}
void Percolate(int X)
{
    int F=X>>1;
    if(F && D[Heap[X]]<D[Heap[F]])
        {
            Swap(X,F);
            Percolate(F);
        }
}
inline double mod(double x)
{
    return max(-x,x);
}
void Solve()
{
    int i,counter=0;

    for(i=1;i<=N;i++)
        {
        Heap[i]=i;
        Poz[i]=i;
        }
    NHeap=N;
    Result[1]=1;
    while(counter<N)
    {
        int pozition=Heap[1];
        Swap(1,NHeap);
        NHeap--;
        Sift(1);
        Use[pozition]=1;
        counter++;
        for(i=0;i<G[pozition].size();i++)
        {
            int vecin=G[pozition][i].first;
            double cost=G[pozition][i].second;
            if(mod(D[vecin]-D[pozition]-cost)<eps)
                Result[vecin]+=Result[pozition],Result[vecin]%=MOD;
            else
                if(D[pozition]+cost<D[vecin])
                {
                    Result[vecin]=Result[pozition];
                    D[vecin]=D[pozition]+cost;
                    Percolate(Poz[vecin]);
                }

        }
    }
    for(int i=2;i<=N;i++)
        g<<Result[i]<<" ";
    g<<"\n";
}
int main()
{
    Read();
    Solve();
    return 0;
}