#include <algorithm>
#include <iostream>
#include <string.h>
#include <vector>
#include <cstdio>
#include <queue>
#include <stack>
using namespace std;
const int inf = 0x3f3f3f3f;
#define maxn 20005
#define maxm 2600005
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct Edge{
	int to,w,next;
}edge[maxm];
struct heapnode{
	int dis,u;
	bool operator < (const heapnode &rhs) const{
		return dis>rhs.dis;
	}
};
int tot=0,head[maxn];
int n,m,k;
void init() {
	tot=0;
	memset(head,-1,sizeof(head));
}
void add(int u,int v,int w) {
	edge[tot].to=v;
	edge[tot].w=w;
	edge[tot].next=head[u];
	head[u]=tot++;
}
int dist[maxn],dist2[maxn];
bool vis[maxn];
int dij(int s) {
	priority_queue<heapnode>q;
	while(!q.empty()) q.pop();
	memset(dist,inf,sizeof(dist));
	memset(vis,false,sizeof(vis));
	dist[s]=0;
	q.push((heapnode) {
		0,s
	});
	while(!q.empty()) {
		heapnode first=q.top();
		q.pop();
		int u=first.u;
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=head[u];i!=-1;i=edge[i].next) {
			int v=edge[i].to;
			if(dist[v]>dist[u]+edge[i].w) {
				dist[v]=dist[u]+edge[i].w;
				q.push((heapnode) {
					dist[v],v
				});
			}
		}
	}
} 
bool G[maxn][maxn],G2[maxn][maxn];
int dp[maxn];
int dfs(int u) {
	if(u==0) return 1;
	if(dp[u]!=-1) return dp[u];
	int ans=0;
	for(int v=0;v<n;v++) {
		if(G2[v][u]) {
			ans+=dfs(v);
		}
	}
	return dp[u]=ans;
}
int main() {
	while(n=read()) {
		if(n==0) break;
		cin>>m;
		init();
		memset(G,0,sizeof(G));
		memset(G2,0,sizeof(G));
		memset(dp,-1,sizeof(dp));
		while(m--) {
			int u,v,w;
			u=read(),v=read(),w=read();
			u--,v--;
			add(u,v,w);
			add(v,u,w);
			G[u][v]=G[v][u]=true;
		}
		dij(1);
		for(int i=0;i<n;i++) {
			for(int j=i+1;j<n;j++) {
				if(dist[j]<dist[i]&&G[i][j]) {
					G2[i][j]=true;
				}
				else if(dist[i]<dist[j]&&G[j][i]) {
					G2[j][i]=true;
				}
			}
		}
		printf("%d\n",dfs(1));
	}
	return 0;
}