#include<stdio.h>
#include<vector>
#include<math.h>
#define eps 0.0000001

const int maxn = 10000;
const int inf = 10000000;

using namespace std;


vector <int>  vect[maxn];
vector <double>  vect2[maxn];
int c;
int h[maxn];
double cost[maxn];
int n;
int m;
int i;
int x,y;
int poz[maxn];
int l;
int nrp[maxn];


int cmpf(int i,int j)
{
        return cost[h[i]]>cost[h[j]];
}


int swap(int i,int j)
{
        int aux=h[i];
        h[i]=h[j];
        h[j]=aux;
        aux=poz[h[i]];
        poz[h[i]]=poz[h[j]];
        poz[h[j]]=aux;
}

void push(int i)
{
        while((cmpf(i,i*2)&&i*2<=l)||(cmpf(i,i*2+1)&&i*2+1<=l))
        {
                if (i*2+1>l||cmpf(i*2+1,i*2))
                {
                        swap(i,i*2);
                        i*=2;
                }
                else
                {
                        swap(i,i*2+1);
                        i=i*2+1;
                }
        }

}
double modul(double i)
{
        if (i<0) return (-1)*i;
        return i;
}


void pop(int i)
{
        while(cmpf(i/2,i)&&i>1)
        {
                swap(i/2,i);
                i/=2;
        }
}


int rem()
{
        int aux=h[1];
        poz[h[1]]=0;
      
        h[1]=h[l];
        h[l]=0;
        poz[h[1]]=1;
        l--;
        push(1);
        return aux;
}


void ad(int i)
{
        l++;
        h[l]=i;
        poz[i]=l;
        pop(i);
}



int main()
{
        freopen("dmin.in","r",stdin);
        freopen("dmin.out","w",stdout);
        scanf("%d %d",&n,&m);
        for(i=1;i<=m;i++)
        {
                scanf("%d %d %d",&x,&y,&c);
                vect[x].push_back(y);
                vect[y].push_back(x);
                vect2[x].push_back(log(c));
                vect2[y].push_back(log(c));

        }
        for(i=2;i<=n;i++)
        {
                cost[i]=inf;

        }
        nrp[1]=1;
        for(i=1;i<=n;i++)
        {
                ad(i);
        }
        while(l)
        {
                x=rem();
                vector <int>:: iterator it;
                vector <double>:: iterator it1;
                for(it=vect[x].begin(), it1=vect2[x].begin();it!=vect[x].end();it++,it1++)
                {
                        if (modul(cost[*it]-cost[x]-(*it1))<=eps)
                        {
                                nrp[*it]=(nrp[*it]+nrp[x])%104659;
                        }
               
                        if (cost[*it]-cost[x]-(*it1)>eps)
                        {
                                cost[*it]=cost[x]+(*it1);
                                nrp[*it]=nrp[x];
                                pop(poz[*it]);
                        }
                }
        }
        for(i=2;i<=n;i++)
        {
                printf("%d ",nrp[i]);
        }
        return 0;
}