#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

/// mst deo

struct grana{
    int a, b, c;
};

bool cmp(grana a, grana b){
    return a.c < b.c;
}

vector <grana> grane;

ll sumw = 0;

int n;
int par[45];
int sz[45];

int root(int x){
    if(par[x] == x) return x;
    return par[x] = root(par[x]);
}

void mst(){
    sort(grane.begin(), grane.end(), cmp);
    for(grana edge : grane){
        int a = edge.a;
        int b = edge.b;
        int c = edge.c;
        int a1 = root(a);
        int b1 = root(b);
        if(a1 == b1) continue;
        sumw += c;
        if(sz[a1] < sz[b1]) swap(a1, b1);
        par[b1] = a1;
        sz[a1] += sz[b1];
    }
}

void clearmst(){
    sumw = 0;
    grane.clear();
    for(int i=1; i<=n; i++){
        par[i] = i;
        sz[i] = 1;
    }
}

/// kraj mst dela

int mat[41][41][251][251];



void Resi(int N, int R, int C, int Q, int** U, int** V, int** W, int* X1, int* Y1, int* X2, int* Y2, int* O){
    n = N;
	for(int i=1; i<=Q; i++) O[i] = -1;
	for(int q=1; q<=Q; q++){
        clearmst();
        for(int i=X1[q]; i<=X2[q]; i++){
            for(int j=Y1[q]; j<=Y2[q]; j++){
                grane.push_back({U[i][j], V[i][j], W[i][j]});
            }
        }
        mst();
        bool ima = 0;
        for(int i=1; i<=n; i++){
            if(sz[i] == n) ima = 1;
        }
        if(ima) O[q] = sumw;
	}
}

/*static int** matrica(int R, int C) {
	int** a = new int*[R+1];
	for (int i=1; i<=R; i++)
		a[i] = new int[C+1];
	return a;
}

static void pocisti(int** a, int R) {
	for (int i=1; i<=R; i++)
		delete[] a[i];
	delete a;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int N, R, C, Q;
	cin >> N >> R >> C >> Q;

	int** U = matrica(R, C);
	int** V = matrica(R, C);
	int** W = matrica(R, C);

	int* X1 = new int[Q+1];
	int* Y1 = new int[Q+1];
	int* X2 = new int[Q+1];
	int* Y2 = new int[Q+1];
	int* O  = new int[Q+1];

	for (int i=1; i<=R; i++)
		for (int j=1; j<=C; j++)
			cin >> U[i][j] >> V[i][j] >> W[i][j];

	for (int i=1; i<=Q; i++)
		cin >> X1[i] >> Y1[i] >> X2[i] >> Y2[i];

	Resi(N, R, C, Q, U, V, W, X1, Y1, X2, Y2, O);

	for (int i=1; i<=Q; i++)
		cout << O[i] << '\n';

	delete[] X1;
	delete[] Y1;
	delete[] X2;
	delete[] Y2;
	delete[] O;

	pocisti(U, R);
	pocisti(V, R);
	pocisti(W, R);
}
*/