Code: Select all
#include <cstdio>
#include <iostream>
#include <vector>
#include <utility>
#include <queue>
#include <cstring>
#define pa pair <int,int>
#define MAX 1010
using namespace std;
vector <pa> v[MAX];
int ver,edg,e1,e2,wed,d[MAX],w[MAX],prev[MAX];
struct com{
bool operator () (const pa &a, const pa &b)
{
return a.second>b.second;
}
};
/*void _print(int node)
{
if(node==-1) return;
cout<<node+1<<" "<<w[node]<<endl;
_print(prev[node]);
}*/
void dijkstra(int src)
{
priority_queue<pa,vector<pa>,com> Q;
memset(d,-1,sizeof(d));
memset(prev,-1,sizeof(prev));
memset(w,0,sizeof(w));
d[src]=0;
w[src]=1;
Q.push(pa(src,0));
while(!Q.empty())
{
pa t=Q.top();Q.pop();
for(int i=0;i<(int)v[t.first].size();i++)
{
if(d[t.first] + v[t.first][i].second < d[v[t.first][i].first] || d[v[t.first][i].first]==-1)
{
d[v[t.first][i].first] = d[t.first] + v[t.first][i].second;
w[v[t.first][i].first] = w[t.first]; //path cal
prev[v[t.first][i].first] = t.first;
Q.push(v[t.first][i]);
}
else if(d[t.first] + v[t.first][i].second == d[v[t.first][i].first])
w[v[t.first][i].first] += w[t.first]; //path cal
}
}
}
int main()
{
//freopen("input.txt","r",stdin);
while(scanf("%d",&ver)==1 && ver)
{
for(int i=0;i<=ver;i++) v[i].clear();
scanf("%d",&edg);
for(int i=0;i<edg;i++)
{
scanf("%d%d%d",&e1,&e2,&wed);
v[e1-1].push_back(pa(e2-1,wed));
v[e2-1].push_back(pa(e1-1,wed));
}
dijkstra(0);
//_print(1);
cout<<w[1];
cout<<endl;
}
return 0;
}