# include # include # include # include # include //# include using namespace std; typedef long long ll; typedef long double ld; typedef vector vi; typedef vector> vvi; typedef vector>> vvvi; typedef vector vl; typedef vector> vvl; typedef vector>> vvvl; typedef vector vb; typedef vector> vvb; typedef vector>> vvvb; #define rep(i,n) for(int i=0;i=0;i--) #define repsr(i,m,n) for(int i=n-1;i>=m;i--) #define replr(i,n) for(ll i=n-1;i>=0;i--) #define repslr(i,m,n) for(ll i=n-1;i>=m;i--) #define sksort(x) sort(x.begin(), x.end()) #define sksortr(x) sort(x.rbegin(), x.rend()) #define disp(x) cout << x << endl #define disps(x) cout << x << " " #define dispe cout << endl #define dispv(x) for(ll xqzj=0;xqzj<(ll)x.size();xqzj++){disps(x[xqzj]);}dispe #define dispvv(x) for(ll xqzi=0;xqzi<(ll)x.size();xqzi++){dispv(x[xqzi]);} #define dispy cout << "Yes" << endl #define dispn cout << "No" << endl #define dispyn(x) if(x)dispy;else dispn #define dispd cout << std::setprecision(20) #define inp(x) int x;cin>>x #define inpl(x) ll x;cin>>x #define inps(x) string x;cin>>x #define allv(x) (x).begin(),(x).end() #define allrv(x) (x).rbegin(),(x).rend() #define imax(x,y) x=max(x,y) #define imin(x,y) x=min(x,y) using mint = atcoder::modint998244353; int main(){ inp(n); inp(m); inp(p); inpl(y); vector> g(n); map,ll> c; vl h(n,1000000000000000001); rep(i,m){ inp(a); inp(b); g[a-1].insert(b-1); g[b-1].insert(a-1); inpl(t); c[{a-1,b-1}]=t; c[{b-1,a-1}]=t; } rep(i,p){ inp(d); inpl(e); h[d-1]=e; } set> st; st.insert({0,0}); vl b(n,1000000000000000001); b[0]=0; while(st.size()>0){ pair q=*st.begin(); st.erase(*st.begin()); for(int i:g[q.second]){ ll x=q.first+c[{q.second,i}]; if(b[i]==1000000000000000001){ b[i]=x; st.insert({b[i],i}); }else if(b[i]>x){ st.erase({b[i],i}); b[i]=x; st.insert({b[i],i}); } } } ll ans=0; rep(i,n)imax(ans,(y-b[i])/h[i]); disp(ans); }