#include <cstdio>
#include <cstring>
#include <climits>
#include <utility>
#include <queue>
#include <vector>
using namespace std;
#define MAX	1005

typedef pair<int,int> PII;
const int OFFICE = 1;
const int HOME   = 2;

int N, M;
vector<PII> neighbour[MAX];
int dis[MAX], path[MAX];
queue<int> q;
bool inq[MAX];

bool init()
{
	if(scanf("%d", &N), !N) return false;
	scanf("%d", &M);

	int i, x, y, d;
	for(i = 1; i <= N; ++i){
		inq[i] = false;
		dis[i] = INT_MAX;
		path[i] = 0;
		neighbour[i].clear();
	}
	for(i = 0; i < M; ++i){
		scanf("%d%d%d", &x, &y, &d);
		neighbour[x].push_back(PII(y, d));
		neighbour[y].push_back(PII(x, d));
	}
	return true;
}
void spfa(int x)
{
	dis[x] = 0;
	q.push(x);
	inq[x] = true;

	while(!q.empty()){
		x = q.front(); q.pop(); inq[x] = false;
		const vector<PII>& v = neighbour[x];
		for(int i = v.size() - 1; i > -1; --i){
			int y = v[i].first, d = v[i].second;
			if(dis[y] > dis[x] + d){
				dis[y] = dis[x] + d;
				if(!inq[y]){
					q.push(y);
					inq[y] = true;
				}
			}
		}
	}
}
int dp(int x)
{
	if(x == HOME) return 1;
	if(path[x]) return path[x];

	const vector<PII>& v = neighbour[x];
	for(int i = v.size() - 1; i > -1; --i){
		int y = v[i].first;
		if(dis[x] > dis[y]) path[x] += dp(y);
	}
	return path[x];
}

int main()
{
	while(init()){
		spfa(HOME);
		printf("%d\n", dp(OFFICE));
	}
}