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

typedef long long ll;

const int INF = 1000000000;

/// mst deo

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

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

vector <grana> grane;

int 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];
int lg[255];
int st[505][505][9];

int findst(int i1, int j1, int i2, int j2){
    int si = lg[i2-i1+1];
    int sj = lg[j2-j1+1];
    int s = min(si, sj);
    vector <int> vi;
    int tren = i1;
    while(tren+(1<<s)-1 < i2){
        vi.push_back(tren);
        tren += (1<<s);
    }
    vi.push_back(i2+1-(1<<s));
    tren = j1;
    vector <int> vj;
    while(tren+(1<<s)-1 < j2){
        vj.push_back(tren);
        tren += (1<<s);
    }
    vj.push_back(j2+1-(1<<s));
    int res = INF;
    int a = vi.size();
    int b = vj.size();
    for(int i=0; i<a; i++){
        for(int j=0; j<b; j++){
            res = min(res, st[vi[i]][vj[j]][s]);
        }
    }
    /*if(si == sj){
        res = min(res, st[i1][j1][s]);
        res = min(res, st[i1][j2+1-(1<<s)][s]);
        res = min(res, st[i1][j2+1-(1<<s)][s];
    }
    for(int i=i1; i<=i2; i++){
        res = min(res, st[i1][j1][s]);
        res = min(res, st[i1][j2+1-(1<<s)][s]);
    }*/
    return res;
}

void resi2(int N, int R, int C, int Q, int** U, int** V, int** W, int* X1, int* Y1, int* X2, int* Y2, int* O){
    for(int i=1; i<=504; i++){
        for(int j=1; j<=504; j++){
            for(int x=0; x<9; x++){
                st[i][j][x] = INF;
            }
        }
    }
    for(int i=1; i<=R; i++){
        for(int j=1; j<=C; j++){
            st[i][j][0] = W[i][j];
        }
    }
    for(int sz=1; (1<<sz)<=C; sz++){
        for(int i=1; i<=R; i++){
            for(int j=1; j<=C; j++){
                st[i][j][sz] = min(st[i][j][sz-1], st[i][j+(1<<(sz-1))][sz-1]);
                st[i][j][sz] = min(st[i][j][sz], st[i+(1<<(sz-1))][j][sz-1]);
                st[i][j][sz] = min(st[i][j][sz], st[i+(1<<(sz-1))][j+(1<<(sz-1))][sz-1]);
            }
        }
    }
    for(int q=1; q<=Q; q++){
        O[q] = findst(X1[q], Y1[q], X2[q], Y2[q]);
    }
    return;
}

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){
    lg[0] = lg[1] = 0;
    for(int i=1; i<=250; i++){
        lg[i] = lg[i/2]+1;
    }
    if(n == 2){
        resi2(N, R, C, Q, U, V, W, X1, Y1, X2, Y2, O);
        return;
    }
    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);
}*/

/*
4 3 4 3
1 2 1  1 2 2  1 2 3  1 2 100
2 3 2  2 3 3  2 3 1  2 3 101
3 4 3  3 4 1  3 4 2  3 4 102
1 1 3 4
1 2 3 3
3 4 3 4
*/

/*
2 3 4 3
1 2 1  1 2 2  1 2 3  1 2 100
2 1 2  2 1 3  2 1 1  2 1 101
1 2 3  1 2 1  1 2 2  1 2 102
1 1 3 4
1 2 3 3
3 4 3 4
*/