#include <fstream.h>
#define nx 500
#define mx 1000
#define bz 104659
ifstream fi("dmin.in");
ofstream fo("dmin.out");

struct muchie
      {int x;
       int y;
       long ct;};

int n,m;
muchie v[mx*2];
int vf[nx];
int sf[nx];
long cmin[nx];
int use[nx];
int dru[nx];
long nrd[mx];
int ord[nx];
int od;

void citire()
    {int i;
     fi>>n>>m;
     for (i=0;i<m;i++)
	{fi>>v[i*2].x>>v[i*2].y>>v[i*2].ct;
	 v[i*2+1].y=v[i*2].x;
	 v[i*2+1].x=v[i*2].y;
	 v[i*2+1].ct=v[i*2].ct;
	 }
     m=m*2;
     fi.close();}

void sortx(int l,int r)
    {int i=l;
     int j=r;
     int w=v[(l+r)/2].x;
     muchie aux;
     do{while (v[i].x<w) i++;
	while (v[j].x>w) j--;
	if (i<=j) {aux=v[i];
		   v[i]=v[j];
		   v[j]=aux;
		   i++;j--;}}
     while (i<=j);
     if (l<j) sortx(l,j);
     if (i<r) sortx(i,r);}

void intervalx()
    {int i;
     vf[v[0].x]=0;
     for (i=1;i<m;i++)
	 if (v[i].x!=v[i-1].x)
	   {sf[v[i-1].x]=i-1;
	    vf[v[i].x]=i;}
     sf[v[m-1].x]=m-1;}

void sortod(int l,int r)
    {int i=l;
     int j=r;
     int aux;
     int w=cmin[ord[(l+r)/2]];
     do{while (cmin[ord[i]]<w) i++;
	while (cmin[ord[j]]>w) 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;
    long long c,w;
    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 (j=vf[a];j<=sf[a];j++)
	   {b=v[j].y;
	    c=v[j].ct;
	    dru[b]=1;
	    w=cmin[a]+c;
	    if (w<cmin[b])
	      {cmin[b]=w;
	       nrd[b]=nrd[a];}
	    else if (w==cmin[b])
		{nrd[b]+=nrd[a];
		 nrd[b]%=bz;}}}
    return r;}

int main()
   {int i,r;
    citire();
    sortx(0,m-1);
    intervalx();

    for (i=2;i<=n;i++)
       {use[i]=0;
	dru[i]=0;
	cmin[i]=3000000000000;}
    for (i=vf[1];i<=sf[1];i++)
       {dru[v[i].y]=1;
	cmin[v[i].y]=v[i].ct;
	nrd[v[i].y]=1;}

    do{r=0;
       r=pas();}
    while (r==1);

    for (i=2;i<n;i++)
	fo<<nrd[i]<<' ';
    fo<<nrd[n]<<'\n';
    fo.close();
    return 0;}