#include using namespace std; using ll = long long; int main(){ ll n,k,m,p; cin>>n>>k>>m>>p; vector> g(n); for(int i = 0;i>u>>v; u--;v--; g[u].push_back(v); g[v].push_back(u); } vector now(n,0); vector s(n); for(int i = 0;i>s[i]; using dat = pair>; priority_queue,greater> que; for(int i = 0;i>x; x--; now[x] = 1; que.push(make_pair(s[x],make_pair(1,x))); que.push(make_pair(p,make_pair(0,x))); } int ans = 0; while(que.size()){ auto nown = que.top(); que.pop(); ll d = nown.first; int t = nown.second.first; int ni = nown.second.second; if(t==1){ if(now[ni]==-1) continue; for(auto&to:g[ni]){ if(now[to]==0){ now[to] = 1; que.push(make_pair(d+s[to],make_pair(1,to))); que.push(make_pair(d+p,make_pair(0,to))); }else if(now[to]==1){ now[to] = -1; ans++; } } }else if(t==0){ now[ni] = 2; } } cout<