#include<stdio.h>
#include<string.h>
#define INF 0x6fffffff
int N,M,i,j;
int p[1005][1005];
int used[1005],mini[1005],sign[1005];
int ans,sum;

void dijkstra()
{
	int k,min,t=1;
	for(i=1;i<=N;i++)
	{
		used[i]=0;
		mini[i]=p[1][i];
	}
	used[1]=1;
	for(k=1;k<N;k++)
	{
		min=INF;
		for(i=1;i<=N;i++)
		{
			if(!used[i] && mini[i]<min)
			{
				min=mini[i];
				t=i;
			}
		}
		used[t]=1;
		for(i=1;i<=N;i++)
		{
			if(!used[i] && (min+p[t][i])<mini[i])
			{
				mini[i]=min+p[t][i];
			}
		}
	}
}

void dfs(int n)
{
	int s;
	sign[n]=1;
	if(n==2 && sum==mini[2])
	{
		ans++;
		return ;
	}
	for(s=1;s<=N;s++)
	{
		if(!sign[s] && sum+p[n][s]<=mini[2])
		{
			sum+=p[n][s];
			dfs(s);
			sum-=p[n][s];
			sign[s]=0;
		}
	}
}

int main()
{
//	freopen("in.txt","r",stdin);
	while(scanf("%d",&N)!=EOF && N)
	{
		scanf("%d",&M);
		int a,b,d;
		ans=0;
		for(i=1;i<=N;i++)
		{
			for(j=1;j<=N;j++)
				p[i][j]=INF;
			p[i][i]=0;
		}
		for(i=1;i<=M;i++)
		{
			scanf("%d%d%d",&a,&b,&d);
			p[a][b]=d;
			p[b][a]=d;
		}
		dijkstra();
		sum=0;
		for(i=1;i<=N;i++)
		{
			sign[i]=0;
		}
		dfs(1);
//		printf("%d\n%d\n",mini[2],ans);
		printf("%d\n",ans);
	}
	return 0;
}