#include<bits/stdc++.h>
using namespace std;
const int mod=1000007,maxn=20005,maxm=200005;
vector<pair<int,int> > g[maxn],f_g[maxn];
int n,m;
int d[maxn],cnt[maxn],cntshort[maxn],vstc[maxn];
bool inq[maxn];
int INF=1e9;
bool fail;
void spfa(int start){
fill(d,d+n,INF);
fill(inq,inq+n,false);
fill(cnt,cnt+n,INF);
fail=false;
d[start]=0;
cnt[start]=0;
inq[start]=true;
queue<int> q;
q.push(start);
while(!fail&&!q.empty()){
int dot=q.front();
q.pop();
inq[dot]=false;
for(int i=0;i<g[dot].size()&&!fail;i++){
int to=g[dot][i].first,weight=g[dot][i].second;
if(d[dot]+weight<d[to]){
d[to]=d[dot]+weight;
cnt[to]=cnt[dot]+1;
if(cnt[to]>n){
fail=true;
break;
}
if(!inq[to]){
inq[to]=true;
q.push(to);
}
}
}
}
}
int Cntshort(int dot){
if(vstc[dot]==1)fail=true;
if(fail)return 0;
if(vstc[dot]==2)return cntshort[dot];
vstc[dot]=1;
for(int i=0;i<f_g[dot].size();i++){
if(d[f_g[dot][i].first]+f_g[dot][i].second==d[dot]){
cntshort[dot]+=Cntshort(f_g[dot][i].first);
}
}
vstc[dot]=2;
return cntshort[dot];
}
int spfa_cnt(int start,int end){
fill(cntshort,cntshort+n,0);
spfa(start);
Cntshort(end);
if(fail)return INF;
cntshort[start]=1;
vstc[start]=2;
return Cntshort(end);
}