#include<fstream>
#define INF 0x3f3f3f3f
#define NN 1501
#define nn  104659
#define eps 0.0000000001
using namespace std;
ofstream out("dmin.out");
int a[NN][NN],drum[NN],v[NN],n,m,d[NN];
void citire();
void dijkstra(int);
int main()
{
	citire();
	dijkstra(1);
	for(int i=2;i<=n;i++)
		out<<drum[i]%nn<<" ";
	return 0;
}
void citire()
{
	ifstream in("dmin.in");
	in>>n>>m;
	int i,j,c;
	for(;m;--m)
	{
		in>>i>>j>>c;
		a[i][j]=a[j][i]=c;
	}
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(a[i][j]==0&&i!=j)
				a[i][j]=a[j][i]=INF;
}
void dijkstra(int s)
{

	int i,j,k,poz;
	for(i=1;i<=n;i++)
	{
		if(a[s][i]>0&a[s][i]!=INF)
			(drum[i]++)%nn;
		d[i]=a[s][i];
	}
	v[s]=1;
		for(i=1;i<n;i++)
		{
			int minim=INF;
				for(j=1;j<=n;j++)
					if(d[j]<minim&&!v[j])
					{
						minim=d[j];
						poz=j;
					}
					v[poz]=1;
						for(k=1;k<=n;k++)
							if(!v[k])
								if(d[k]>d[poz]+a[poz][k]&&a[poz][k]!=INF)
								{
									drum[k]=drum[poz]%nn;
									d[k]=d[poz]+a[poz][k];
									
								}
								else
									if(d[k]==d[poz]+a[poz][k]&&a[poz][k]!=INF)
										drum[k]+=drum[poz]%nn;
		}
}