#include <math.h>
#include <stdio.h>
#define mx 1502
#define bz 104659
#define aprox 0.0001
FILE *fi=fopen("dmin.in","r");
FILE *fo=fopen("dmin.out","w");

struct muchie
      {int y;
       double ct;
       muchie *next;};

int m,n;
muchie *v[mx];

double cmin[mx];
long nrd[mx];

int use[mx];
int dru[mx];

int ord[mx];
int od;

double abs(double k)
      {if (k<0) return -k;
       return k;}

void adaug(muchie *&k,int b,double c)
    {muchie *p;
     p=new muchie;
     p->y=b;
     p->ct=c;
     p->next=k;
     k=p;}

void citire()
    {int i;
     int a,b;
     long c;
     double r;
     fscanf(fi,"%d%d",&n,&m);
     for (i=0;i<m;i++)
	{fscanf(fi,"%d%d%ld",&a,&b,&c);
	 r=log10(c);
	 adaug(v[a],b,r);
	 adaug(v[b],a,r);}
     fclose(fi);}

void nullif(muchie *&k)
    {muchie *p;
     while (k!=NULL)
	  {p=k;
	   k=k->next;
	   delete p;}}

void sortod(int l,int r)
    {int i=l;
     int j=r;
     int aux;
     double w=cmin[ord[(l+r)/2]];
     do{while (cmin[ord[i]]<w && (w-cmin[ord[i]]>aprox)) i++;
	while (cmin[ord[j]]>w && (cmin[ord[j]]-w>aprox)) j--;
	if (i<=j) {aux=ord[i];
		   ord[i]=j;
		   ord[j]=aux;
		   i++;j--;}}
     while (i<=j);
     if (l<j) sortod(l,j);
     if (i<r) sortod(i,r);}

int pas()
   {int i,j;
    int r=0;
    int a,b;
    double c,w;
    muchie *p;
    od=0;
    for (i=2;i<=n;i++)
	if (use[i]==0 && dru[i]==1)
	  {ord[od]=i;
	   use[i]=1;
	   r=1;
	   od++;}
    sortod(0,od-1);
    for (i=0;i<od;i++)
       {a=ord[i];
	for (p=v[a];p!=NULL;p=p->next)
	   {b=p->y;
	    c=p->ct;
	    dru[b]=1;
	    w=cmin[a]+c;
	    if (w<cmin[b] && (cmin[b]-w>aprox))
	      {cmin[b]=w;
	       nrd[b]=nrd[a];}
	    else if (abs(cmin[b]-w)<aprox)
		{nrd[b]+=nrd[a];
		 nrd[b]%=bz;}}}
    return r;}

int main()
   {int i,r;
    muchie *p;
    citire();
    for (i=2;i<=n;i++)
       {use[i]=0;
	dru[i]=0;
	cmin[i]=2000000000;}
    for (p=v[1];p!=NULL;p=p->next)
       {dru[p->y]=1;
	cmin[p->y]=p->ct;
	nrd[p->y]=1;}
    do{r=0;
       r=pas();}
    while (r==1);
    for (i=2;i<n;i++)
	fprintf(fo,"%ld ",nrd[i]);
    fprintf(fo,"%ld\n",nrd[n]);
    for (i=1;i<=n;i++)
	nullif(v[i]);
    fclose(fo);
    return 0;}