#include <cstdio>
#include <fstream>
#include <queue>
#include <cmath>
#define inff 0x3f3f3f
#define MAX_N 50001

using namespace std;

struct nod
{
     long double  cost;
     long n;
};

vector <nod> V[MAX_N];
queue <long long> Q;
char viz[MAX_N];
long long N,M,cati[MAX_N];
long double D[MAX_N];

void citire()
{
    long long x,y,z;
    scanf("%lld %lld",&N,&M);
    for(long long i = 1; i <= M; ++i)
    {
        scanf("%lld %lld %lld",&x,&y,&z);
        nod t;
        t.n = y;
        t.cost = log(z);
        V[x].push_back(t);
        t.n=x;
        t.cost= log(z);
        V[y].push_back(t);
    }
}

void solve()
{
     for (int i=0;i<=N;i++)
          D[i]=1000000000;
    Q.push(1);
    D[1] = 1;
    cati[1]=1;
    viz[1] ='1';
    while(!Q.empty())
    {
        long long nod = Q.front();
        Q.pop();
        viz[nod]='0';

        for(typeof V[nod].begin() p = V[nod].begin(); p < V[nod].end(); p++)
            if(D[p->n]>D[nod]+p->cost)
            {
                 cati[p->n]=cati[nod];
                D[p->n]=D[nod]+p->cost;
                if(viz[p->n]!='1')
                {
                    Q.push(p->n);
                    viz[p->n]='1';
                }
            }
            else
               if (D[p->n]==D[nod]+p->cost)
                    cati[p->n]+=cati[nod];
    }
}
void afisare()
{

    for(long long i = 2; i <= N; ++i)
      printf("%lld ",cati[i]%104659);
    printf("\n");
}

int main()
{
    freopen ("dmin.in","r",stdin);
    freopen ("dmin.out","w",stdout);
    citire();
    solve();
    afisare();
    return 0;
}