#include<stdio.h>
#include<vector>
#include<set>
#include<math.h>
using namespace std;
#define nmax 1505
#define modulo 104659
#define eps 0.0000001
struct element {long n; double c;};
long n, m, i, a, b, c, ndr[nmax], nod;
double cost, dmin[nmax], dif;
vector <element> ma[nmax];
vector <element> ::iterator it;
element el;
set <pair <double, long> > h;
pair <double, long> x;


void citire()
{
    scanf("%ld %ld",&n,&m);
    for (i=1;i<=m;i++)
    {
        scanf("%ld %ld %ld",&a,&b,&c);
        el.n=b; el.c=log(c); ma[a].push_back(el);
        el.n=a; el.c=log(c); ma[b].push_back(el);
    }
}

void rezolvare()
{
    ndr[1]=1;
    for (it=ma[1].begin();it!=ma[1].end();it++)
    {
        h.insert(make_pair((*it).c,(*it).n));
        dmin[(*it).n]=(*it).c;  ndr[(*it).n]=1;
    }
    while (h.size())
    {
        x=*h.begin();    h.erase(h.begin());
        for (it=ma[x.second].begin();it!=ma[x.second].end();it++)
            if ((*it).n>1)
            {
                nod=(*it).n;    cost=(*it).c;
                dif=dmin[nod]-(dmin[x.second]+cost);
                if ((dif>eps) || (dmin[nod]==0))
                {
                    h.erase(make_pair(dmin[nod],nod));
                    dmin[nod]=dmin[x.second]+cost;   ndr[nod]=ndr[x.second];
                    h.insert(make_pair(dmin[nod],nod));
                }
                else
                {
                    if (dif<0)
                        dif=-dif;
                    if (dif<=eps)
                    {
                        ndr[nod]=ndr[nod]+ndr[x.second];
                        if (ndr[nod]>modulo)
                            ndr[nod]-=modulo;
                    }
                }
            }
    }
}

int main()
{
    freopen("dmin.in","r",stdin);
    freopen("dmin.out","w",stdout);
    citire();
    rezolvare();
    for (i=2;i<=n;i++)
        printf("%ld ",ndr[i]);
    return 0;
}