#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[5][5][251][251*4];
//int ok[41][41][251][251*4];
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 update(int n1,int n2,int col,int l,int r,int x,int ind,int val){
    if (x>r or x<l)return;
    if (l==r){
        seg[n1][n2][col][ind]=val;
        return;
    }
    int mid=(l+r)/2;
    update(n1,n2,col,l,mid,x,ind*2,val);
    update(n1,n2,col,mid+1,r,x,ind*2+1,val);

    seg[n1][n2][col][ind]=min(seg[n1][n2][col][ind*2],seg[n1][n2][col][ind*2+1]);
    //cout<<n1<<" "<<n2<<" "<<col<<" "<<ind<<" "<<seg[n1][n2][col][ind]<<"\n";
}
int calc(int n1,int n2,int col,int l,int r,int x,int y,int ind,int f){
    if (x>r or y<l)return 1e9;
    //if (f==3)cout<<n1<<" "<<n2<<" "<<col<<" "<<ind<<" "<<seg[n1][n2][col][ind]<<"\n";
    if (l>=x and r<=y){
        return seg[n1][n2][col][ind];
    }
    int mid=(l+r)/2;
    return min(calc(n1,n2,col,l,mid,x,y,ind*2,f),calc(n1,n2,col,mid+1,r,x,y,ind*2+1,f));
}

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
	for (int i=1;i<=4;i++){
        for (int j=1;j<=4;j++){
            for (int p=1;p<=250;p++){
                for (int k=1;k<=250*4;k++){
                    seg[i][j][p][k]=1e9;
                }
            }
        }
	}

    //Za N=2 i N=3
    if (N<=4){
        //napravi seg
        for (int i=1;i<=R;i++){
            for (int j=1;j<=C;j++){
                if (U[i][j]>V[i][j])swap(U[i][j],V[i][j]);
                update(U[i][j],V[i][j],i,1,C,j,1,W[i][j]);
            }
        }

        for (int f=1;f<=Q;f++){
            for (int i=1;i<=N;i++){
                sz[i]=1;
                dsu[i]=i;
                ans[i]=0;
            }
            s.clear();
            for (int j=1;j<=N;j++){
                for (int p=j+1;p<=N;p++){
                    for (int i=X1[f];i<=X2[f];i++){
                        int x=calc(j,p,i,1,C,Y1[f],Y2[f],1,f);
                        if (x!=1e9)s.insert({x,{j,p}});
                    }
                }
            }
            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];
        }
        return;
    }


	//za Prva dva podzadatka
    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];

        //cout<<O[f]<<" ";
    }
}


/*
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


2 4 4 1
1 2 2
1 2 1
1 2 1
1 2 1
1 2 1
1 2 3
1 2 3
1 2 5
1 2 3
1 2 4
1 2 3
1 2 12
1 2 4
1 2 2
1 2 8
1 2 10
2 2 3 3
1 1 1 4
3 3 3 4

3 3 4 3
1 3 3
1 2 5
2 3 4
1 2 2
1 3 5
1 3 6
2 3 2
2 1 2
1 2 4
1 2 1
2 3 1
1 3 1
2 2 3 3
1 2 2 4
1 4 2 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;
}

*/