#include #include #include #include #include #include #include #include #include using namespace std; int n,m,s,len; vector > g[100001]; int d[100001]; priority_queue > pq; int main() { scanf("%d %d %d",&n,&m,&s); for (int i=0;i p = pq.top(); int id=p.second; int idd=-p.first; pq.pop(); if (d[id]!=idd) continue; for (int i=0;i<(int)g[id].size();i++) { int id2=g[id][i].first; int w=g[id][i].second; if (d[id2]==-1 || d[id]+w=len) st++; if (0len) st++; } } printf("%d\n",st); return 0; }