#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 41;

struct grana{
    ll u,v,w;
};

vector <ll> g[N];
vector <grana> grane;
ll par[N],rnk[N],cmpcnt = 0;

ll findset(ll x){
    return (par[x] == x ? x : par[x] = findset(par[x]));
}

bool sameset(ll x,ll y){
    return (findset(x) == findset(y));
}

void unionset(ll x,ll y){
    ll s1 = findset(x),s2 = findset(y);
    if(s1 != s2){
        if(rnk[s1] > rnk[s2]){
            par[s2] = s1;
        }
        else{
            par[s1] = s2;
            if(rnk[s1] == rnk[s2]){
                rnk[s1]++;
            }
        }
    }
}

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

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){
    int n = N;
    for(int i = 1; i <= Q; i++){
        int x1 = X1[i],x2 = X2[i],y1 = Y1[i],y2 = Y2[i];\
        grane.clear();
        for(int j = x1; j <= x2; j++){
            for(int k = y1; k <= y2; k++){
                grane.push_back({U[j][k],V[j][k],W[j][k]});
            }
        }
        sort(grane.begin(),grane.end(),cmp);
        for(int i = 1; i <= n; i++){
            par[i] = i;
            rnk[i] = 0;
        }
        cmpcnt = n;
        ll sol = 0;
        for(int i = 0; i < grane.size(); i++){
            ll x = grane[i].u,y = grane[i].v,cost = grane[i].w;
            if(!sameset(x,y)){
                cmpcnt--;
                unionset(x,y);
                sol += cost;
            }
        }
        if(cmpcnt == 1){
            O[i] = sol;
        }
        else{
            O[i] = -1;
        }
    }
}