#include <bits/stdc++.h>

#define ll long long
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back

using namespace std;

int seg[251][251*5];
int sz[41],dsu[41];
ll ans[41];
set<pair<int,pair<int,int>>>s;

int root(int s){
    while(s!=dsu[s]){
        s=dsu[s];
        dsu[s]=dsu[dsu[s]];
    }
    return s;
}
void spoj(int a,int b,ll dodaj){
    if (sz[a]<sz[b])swap(a,b);
    sz[a]+=sz[b];
    dsu[b]=a;
    ans[a]+=ans[b]+dodaj;
}
void mst(){
    for (auto i:s){
        int a=root(i.se.fi);
        int b=root(i.se.se);

        if (a==b)continue;
        spoj(a,b,(ll)i.fi);
    }
}

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){

	//inicijalizuj
	memset(seg,1e9,sizeof(seg));

    for (int f=1;f<=Q;f++){
        for (int i=1;i<=40;i++){
            sz[i]=1;
            dsu[i]=i;
            ans[i]=0;
        }
        s.clear();
        for (int i=X1[f];i<=X2[f];i++){
            for (int j=Y1[f];j<=Y2[f];j++){
                s.insert({W[i][j],{U[i][j],V[i][j]}});
            }
        }
        mst();
        //for (auto i:s)cout<<i.fi<<" "<<i.se.fi<<" "<<i.se.se<<"\n";
        int t=root(1);
        if(sz[t]!=N)O[f]=-1;
        else O[f]=ans[t];
    }
}

/*
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;
}
int main(){
    ios;
/*
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

	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);
    return 0;
}
*/