#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define N 1501
#define INF 0x3f3f3f3f
#define MOD 104659
#define COMP 0.0000001
using namespace std;

struct graf
{
    int n;
    double cost;
    graf *next;
};

graf *a[N];
int poz[N], sol[N], h[N];
int k;
double d[N];

double md(double r)
{
    if(r<0) return -r;
    return r;
}

void gadd(int x, int y, double cost)
{
    graf *p=new graf;
    p->n=y;
    p->cost=cost;
    p->next=a[x];
    a[x]=p;

    p=new graf;
    p->n=x;
    p->cost=cost;
    p->next=a[y];
    a[y]=p;
}

void upheap(int what)
{
    int tata;
    while ( what > 1 )
    {
        tata = what >> 1;

        if ( d[ h[tata] ] > d[ h[what] ] )
        {
            poz[ h[what] ] = tata;
            poz[ h[tata] ] = what;

            swap(h[tata], h[what]);

            what = tata;
        }
        else
            what = 1;
    }
}

void downheap(int what)
{
    int f;
    while ( what <= k )
    {
        f = what;
        if ( (what<<1) <= k )
        {
            f = what << 1;
            if ( f + 1 <= k )
                if ( d[ h[f + 1] ] < d[ h[f] ] )
                    ++f;
        }
        else
            return;

        if ( d[ h[what] ] > d[ h[f] ] )
        {
            poz[ h[what] ] = f;
            poz[ h[f] ] = what;

            swap(h[what], h[f]);

            what = f;
        }
        else
            return;
    }
}

int main()
{
    freopen("dmin.in", "r", stdin);
    freopen("dmin.out", "w", stdout);
    int n, m, i, x, y, mins, c;
    double cost;
    graf *p=new graf;
    scanf("%d%d", &n, &m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d", &x, &y, &c);
        cost=log(double(c));
        //printf("%lf ", cost);
        gadd(x, y, cost);
    }
    for(i=2;i<=n;i++)
    {
        d[i]=INF;
    }
    h[++k]=1;
    poz[1]=1;
    sol[1]=1;
    while(k)
    {
        mins=h[1];
        swap(h[1], h[k]);
        poz[h[1]]=1;
        k--;
        downheap(1);
        for(p=a[mins];p;p=p->next)
        {
            if(d[p->n]-d[mins]-p->cost>COMP)
            {
                d[p->n]=d[mins]+p->cost;
                if(poz[p->n])
                {
                    upheap(poz[p->n]);
                }
                else
                {
                    h[++k]=p->n;
                    poz[p->n]=k;
                    upheap(k);
                }
                sol[p->n]=sol[mins];
            }
            else if(md(d[mins]+p->cost-d[p->n])<COMP)
            {
                sol[p->n]=(sol[p->n]+sol[mins])%MOD;
                //printf("%d ", mins);
            }
        }
    }
    for(i=2;i<=n;i++)
    {
        printf("%d ", sol[i]);
    }
}