hdu1142

/*
분석:
흥분해 죽겠어요.
보름 전에 본 문제는 그때 반만 썼을 뿐, 당시의 사고방식의 마지막 단계는 쌓아야 했다.
보조하다.오늘 이 문제를 다시 보니, 갑자기... 쌓지 않아도 된다는 것을 발견하였다. 비록 0.0이 쌓였지만
제목이 어렵지 않으니 인터넷상에서 소와 소의 사고방식을 보아라, 풋내기는 추태를 보이지 않을 것이다
내일이면 기말고사인데 반찬은 여기서 코드를 두드리고 끊을게요 T^T~
그러나 한 교실에서 나 혼자만 음악을 듣고 코드를 두드리는 것은 아니다
처음이에요. 이 느낌 좋네요.
                                                         2012-06-24
*/

#include"stdio.h"
#include"string.h"
#include"stdlib.h"
struct A
{
	int dis;
	int flag;
}E[1001];
struct B
{
	int dis;
	int num;
}T[1001];
int map[1001][1001];
int cmp(const struct B *a,const struct B *b)
{
	return b->dis-a->dis;
}
int main()
{
	int n,m;
	int i,l;
	int k;
	int a,b,d;
	int hash[1001];
	int ans[1001];
	while(scanf("%d",&n),n)
	{
		scanf("%d",&m);

		for(i=1;i<=n;i++)
		for(l=1;l<=n;l++)
			map[i][l]=0;
		for(i=0;i<m;i++)
		{
			scanf("%d%d%d",&a,&b,&d);
			map[a][b]=map[b][a]=d;
		}

		for(i=1;i<=n;i++)
		{
			E[i].dis=11111111;
			E[i].flag=1;
		}

		k=2;
		E[k].dis=0;
		while(k)
		{
			E[k].flag=0;
			if(E[k].dis>E[1].dis)	break;
			for(i=1;i<=n;i++)
			{
				if(map[i][k]==0)	continue;
				if(E[k].dis+map[i][k]<E[i].dis)	E[i].dis=E[k].dis+map[i][k];
			}
			k=0;
			for(i=1;i<=n;i++)	if(E[i].flag)	{k=i;break;}
			for(i++;i<=n;i++)	if(E[i].flag&&E[i].dis<E[k].dis)	k=i;
		}


		if(E[1].dis==11111111)	{printf("0
");continue;}


		memset(hash,0,sizeof(hash));
		T[0].num=1;
		T[0].dis=E[1].dis;
		k=1;
		hash[1]=1;
		for(i=2;i<=n;i++)
		{
			if(E[i].dis>=E[1].dis)	continue;
			T[k].num=i;
			T[k].dis=E[i].dis;
			hash[i]=1;
			k++;
		}
		qsort(T,k,sizeof(T[0]),cmp);

		for(i=1;i<=n;i++)	ans[i]=0;
		ans[1]=1;
		for(i=0;i<k;i++)
		{
			if(ans[T[i].num]==0)continue;
			for(l=1;l<=n;l++)	if(hash[l]==1&&map[T[i].num][l]!=0&&E[l].dis<T[i].dis)	ans[l]+=ans[T[i].num];
		}

		printf("%d
",ans[2]);
	}
	return 0;
}