题意 ：办公室编号为1，家编号为2，问从办公室到家有多少条路径，当然路径要短，从A走到B的条件是，A到家比B到家要远，所以可以从A走向B 。
思路 ： 先以终点为起点求最短路，然后记忆化搜索。
//
#include <cstdio>
#include <queue>
#include <cstring>
#include <iostream>
const int INF = << ;
using namespace std ; int N,M ;
int mapp[][] ,pre[],dist[];
bool vis[] ; void spfa(int src)
{
for(int i = ; i <= N ; i++)
{
vis[i] = false ;
dist[i] = INF ;
}
queue<int>Q ;
dist[src] = ;
vis[src] = true ;
Q.push(src) ;
while(!Q.empty())
{
int u = Q.front() ;
Q.pop() ;
vis[u] = false ;
for(int i = ; i <= N ; i++)
{
if(dist[i] > dist[u] + mapp[u][i] && mapp[u][i] != INF)
{
dist[i] = dist[u] + mapp[u][i] ;
if(!vis[i])
{
vis[i] = true ;
Q.push(i) ;
}
}
}
}
}
int dfs(int s)
{
if(pre[s]) return pre[s];
if(s == ) return ;
int cnt = ;
for(int i = ;i <= N ; i++)
{
if(mapp[s][i] < INF && dist[s] > dist[i])
{
if(pre[i]) cnt += pre[i];//已经找过了
else cnt += dfs(i);
}
}
pre[s] = cnt ;
return pre[s];
}
void Init()
{
for(int i = ; i <= N ; i++)
for(int j = ; j <= N ; j++)
{
if(i == j) mapp[i][j] = ;
else mapp[i][j] = INF ;
}
memset(pre,,sizeof(pre)) ;
}
int main()
{
while(cin >> N)
{
if(N == ) break ;
cin >> M ;
Init() ;
int u,v,w ;
while(M--)
{
cin >> u >> v >> w ;
mapp[u][v] = mapp[v][u] = w ;
}
spfa() ;
cout << dfs() << endl ;
}
return ;
}