// Author: kyEEcccccc

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>

using namespace std;
using __gnu_pbds::gp_hash_table;

using LL = long long;
using ULL = unsigned long long;

#define F(i, l, r) for (int i = (l); i <= (r); ++i)
#define FF(i, r, l) for (int i = (r); i >= (l); --i)
#define MAX(a, b) ((a) = max(a, b))
#define MIN(a, b) ((a) = min(a, b))
#define SZ(a) ((int)((a).size()) - 1)

constexpr int N = 200005;

struct Edge
{
	int u, v;
	int l;
};

int n, ma, mb;
LL lim;
Edge ea[N], eb[N];

int ida[N], idb[N];
vector<int> pa[N], pb[N];
cc_hash_table<int, int> cnta[N], cntb[N];
int tar[N], from[N], num[N];

LL perf(int i)
{
	int t1 = ida[ea[i].u], t2 = ida[ea[i].v];
	if (t1 == t2) return 0;
	if (pa[t1].size() > pa[t2].size()) swap(t1, t2);
	LL res = (LL)pa[t1].size() * (LL)pa[t2].size();
	for (auto x : pa[t2]) res -= cnta[t1][idb[x]];
	for (auto x : pa[t2])
	{
		pa[t1].push_back(x);
		ida[x] = t1;
		cnta[t1][idb[x]] += 1;
		if ((cntb[idb[x]][t2] -= 1) == 0) cntb[idb[x]].erase(t2);
		cntb[idb[x]][t1] += 1;
	}
	cnta[t2].clear();
	pa[t2].clear();
	return res;
}

LL redo(int i)
{
	if (tar[i] == -1) return 0;
	int t1 = tar[i], t2 = from[i];
	assert(pb[t2].empty());
	F(_, 1, num[i])
	{
		int x = pb[t1].back();
		idb[x] = t2;
		cntb[t2][ida[x]] += 1;
		if ((cntb[t1][ida[x]] -= 1) == 0) cntb[t1].erase(ida[x]);
		if ((cnta[ida[x]][t1] -= 1) == 0) cnta[ida[x]].erase(t1);
		cnta[ida[x]][t2] += 1;
		pb[t2].push_back(x);
		pb[t1].pop_back();
	}
	reverse(pb[from[i]].begin(), pb[from[i]].end());
	LL res = (LL)pb[t1].size() * (LL)pb[t2].size();
	for (auto x : pb[t2]) res -= cntb[t1][ida[x]];
	return res;
}

signed main(void)
{
	// freopen(".in", "r", stdin);
	// freopen(".out", "w", stdout);
	ios::sync_with_stdio(0), cin.tie(nullptr);

	cin >> n >> ma >> mb >> lim;
	F(i, 1, ma) cin >> ea[i].u >> ea[i].v >> ea[i].l;
	F(i, 1, mb) cin >> eb[i].u >> eb[i].v >> eb[i].l;

	sort(ea + 1, ea + ma + 1, [] (Edge x, Edge y) { return x.l < y.l; });
	sort(eb + 1, eb + mb + 1, [] (Edge x, Edge y) { return x.l < y.l; });

	F(i, 1, n)
	{
		idb[i] = i;
		pb[i].push_back(i);
	}
	F(i, 1, mb)
	{
		int t1 = idb[eb[i].u], t2 = idb[eb[i].v];
		if (t1 == t2)
		{
			tar[i] = -1;
			continue;
		}
		if (pb[t1].size() < pb[t2].size()) swap(t1, t2);
		tar[i] = t1, from[i] = t2;
		num[i] = pb[t2].size();
		for (auto x : pb[t2])
		{
			pb[t1].push_back(x);
			idb[x] = t1;
		}
		pb[t2].clear();
	}
	F(i, 1, n)
	{
		cntb[idb[i]][i] += 1;

		ida[i] = i;
		pa[i].push_back(i);
		cnta[i][idb[i]] += 1;
	}
	LL cur = 0;
	F(i, 1, n)
	{
		LL t = pb[i].size();
		cur += t * (t - 1) / 2;
	}

	int j = mb;
	int ans = INT_MAX;
	F(i, 0, ma)
	{
		if (i != 0) cur += perf(i);
		while (j > 0 && cur >= lim)
		{
			cur -= redo(j);
			--j;
		}

		if (j == mb && cur < lim) continue;
		if (cur >= lim) MIN(ans, i == 0 ? 0 : ea[i].l);
		else MIN(ans, (i == 0 ? 0 : ea[i].l) + eb[j + 1].l);
	}
	if (ans != INT_MAX) cout << ans << '\n';
	else cout << "-1\n";
	
	return 0;
}

answer.code:33:1: error: ‘cc_hash_table’ does not name a type; did you mean ‘gp_hash_table’?
   33 | cc_hash_table<int, int> cnta[N], cntb[N];
      | ^~~~~~~~~~~~~
      | gp_hash_table
answer.code: In function ‘LL perf(int)’:
answer.code:42:38: error: ‘cnta’ was not declared in this scope
   42 |         for (auto x : pa[t2]) res -= cnta[t1][idb[x]];
      |                                      ^~~~
answer.code:47:17: error: ‘cnta’ was not declared in this scope
   47 |                 cnta[t1][idb[x]] += 1;
      |                 ^~~~
answer.code:48:22: error: ‘cntb’ was not declared in this scope
   48 |                 if ((cntb[idb[x]][t2] -= 1) == 0) cntb[idb[x]].erase(t2);
      |                      ^~~~
answer.code:49:17: error: ‘cntb’ was not declared in this scope
   49 |                 cntb[idb[x]][t1] += 1;
      |                 ^~~~
answer.code:51:9: error: ‘cnta’ was not declared in this scope
   51 |         cnta[t2].clear();
      |         ^~~~
answer.code: In function ‘LL redo(int)’:
answer.code:65:17: error: ‘cntb’ was not declared in this scope
   65 |                 cntb[t2][ida[x]] += 1;
      |                 ^~~~
answer.code:67:22: error: ‘cnta’ was not declared in this scope
   67 |                 if ((cnta[ida[x]][t1] -= 1) == 0) cnta[ida[x]].erase(t1);
      |                      ^~~~
answer.code:68:17: error: ‘cnta’ was not declared in this scope
   68 |                 cnta[ida[x]][t2] += 1;
      |                 ^~~~
answer.code:74:38: error: ‘cntb’ was not declared in this scope
   74 |         for (auto x : pb[t2]) res -= cntb[t1][ida[x]];
      |                                      ^~~~
answer.code: In function ‘int main()’:
answer.code:116:17: error: ‘cntb’ was not declared in this scope
  116 |                 cntb[idb[i]][i] += 1;
      |                 ^~~~
answer.code:120:17: error: ‘cnta’ was not declared in this scope
  120 |                 cnta[i][idb[i]] += 1;
      |                 ^~~~