#include <cstdio>
#include <vector>
#include <cmath>
#define Nmax 1505
#define INF 2000000000
#define eps 0.000001
#define MOD 104659

using namespace std;

int N,H[Nmax],poz[Nmax],nr[Nmax];
double d[Nmax];

struct coord
{
    int n;
    double cost;
};
vector <coord> L[Nmax];

inline void Swap(int i, int j)
{
    int hi=H[i],hj=H[j];
    H[i]=hj; H[j]=hi;
    poz[hi]=j; poz[hj]=i;
}

inline void DownHeap(int k)
{
    int fiu,gata;
    fiu=2*k; gata=0;
    while(k<=H[0]/2 && !gata)
    {
        if(fiu+1<=H[0] && eps+d[H[fiu+1]]<d[H[fiu]])
            ++fiu;
        if(eps+d[H[k]]<=d[H[fiu]])
            gata=1;
        else
        {
            Swap(k,fiu);
            k=fiu; fiu=2*k;
        }
    }
}

inline void UpHeap(int k)
{
    int tata;
    tata=k/2;
    while(k>1 && eps+d[H[k]]<d[H[tata]])
    {
        Swap(k,tata);
        k=tata; tata=k/2;
    }
}

int main()
{
    int M,x,y,z,i,len,nod,j;
    coord w;
    freopen ("dmin.in","r",stdin);
    freopen ("dmin.out","w",stdout);
    scanf("%d%d", &N,&M);
    while(M--)
    {
        scanf("%d%d%d", &x,&y,&z);
        w.n=y; w.cost=log(z);
        L[x].push_back(w);
        w.n=x;
        L[y].push_back(w);
    }

    for(i=2;i<=N;++i)
    {
        d[i]=INF;
        poz[i]=-1;
    }
    H[++H[0]]=1; poz[1]=1;
    nr[1]=1;
    while(H[0])
    {
        nod=H[1]; len=L[nod].size();
        H[1]=H[H[0]--];
        DownHeap(1);
        for(i=0;i<len;++i)
        {
            j=L[nod][i].n;
            if(d[j]>d[nod]+L[nod][i].cost+eps)
            {
                d[j]=d[nod]+L[nod][i].cost;
                nr[j]=nr[nod];
                if(poz[j]!=-1)
                    UpHeap(poz[j]);
                else
                {
                    H[++H[0]]=j; poz[j]=H[0];
                    UpHeap(H[0]);
                }
            }
            else
                if(fabs(d[j]-(d[nod]+L[nod][i].cost))<=eps)
                {
                    nr[j]+=nr[nod];
                    if(nr[j]>=MOD)
                        nr[j]-=MOD;
                }
        }
    }
    for(i=2;i<=N;++i)
        printf("%d ", nr[i]);
    printf("\n");
    return 0;
}