#include<bits/stdc++.h> using namespace std; #define int long long #define ii pair<int,int> #define aa array<int,3> #define fir first #define sec second #define pb push_back const int maxn=2e5; int n,a,b,k; vector<aa>edgea,edgeb; int dsu[maxn+2],tot; vector<int>node[maxn+2]; int fin(int a){ return dsu[a]; } vector<aa> merg(int a,int b){ a=dsu[a],b=dsu[b]; if(a==b)return{}; tot+=(node[a].size() * node[b].size()); vector<aa>event; if(node[a].size()>node[b].size())swap(a,b); for(auto x : node[a]){ node[b].pb(x); event.pb({x,a,b}); dsu[x]=b; } node[a].clear(); return event; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>n>>a>>b>>k; if(k==0){ cout<<0<<endl; return 0; } for(int q=1;q<=a;q++){ int u,v,w; cin>>u>>v>>w; edgea.pb({w,u,v}); } for(int q=1;q<=b;q++){ int u,v,w; cin>>u>>v>>w; edgeb.pb({w,u,v}); } sort(edgea.begin(),edgea.end()); sort(edgeb.begin(),edgeb.end()); tot=0;int ans=1e18; for(int q=1;q<=n;q++){ dsu[q]=q; node[q]={q}; } vector<aa>eva[a+1]; int hasa[a+1]; for(int q=0;q<edgea.size();q++){ auto [w,u,v]=edgea[q]; eva[q+1]=merg(u,v); hasa[q+1]=tot; if(tot>=k)ans=min(ans,w); } tot=0; for(int q=1;q<=n;q++){ dsu[q]=q; node[q]={q}; } vector<aa>evb[b+1]; int hasb[b+1]; for(int q=0;q<edgeb.size();q++){ auto [w,u,v]=edgeb[q]; evb[q+1]=merg(u,v); hasb[q+1]=tot; if(tot>=k)ans=min(ans,w); } int para[n+1],parb[n+1]; map<ii,int>mp; int sama=0,pos=b; for(int q=1;q<=n;q++){ para[q]=q; parb[q]=dsu[q]; mp[{para[q],parb[q]}]++; } for(int q=1;q<=a;q++){ for(auto [u,prv,nxt] : eva[q]){ mp[{para[u],parb[u]}]--; sama-=mp[{para[u],parb[u]}]; para[u]=nxt; sama+=mp[{para[u],parb[u]}]; mp[{para[u],parb[u]}]++; } // cout<<q<<" "<<sama<<" k "<<hasb[pos]<<endl; while(pos && hasa[q]+hasb[pos]-sama>=k){ // cout<<q<<" "<<pos<<" "<<hasa[q]+hasb[pos]-sama<<endl; for(auto [u,prv,nxt] : evb[pos]){ mp[{para[u],parb[u]}]--; sama-=mp[{para[u],parb[u]}]; parb[u]=prv; sama+=mp[{para[u],parb[u]}]; mp[{para[u],parb[u]}]++; } pos--; } if(pos<b){ ans=min(ans,edgea[q-1][0]+edgeb[pos][0]); } } if(ans==1e18)ans=-1; cout<<ans<<endl; }