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

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

vector <int> g[N];
vector <grana> grane;
int par[N],rnk[N],cmpcnt = 0;
int sp[R][R][9],logs[R],n,r,c;

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

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

void unionset(ll x,ll y){
    int 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;
}

ll getmin(ll x1,ll x2,ll y1,ll y2){
    ll sol = inf;
    for(int i = x1; i <= x2; i++){
        ll r = logs[y2-y1+1];
        ll rez = min(sp[i][y1][r],sp[i][y2-(1<<r)+1][r]);
        sol = min(sol,rez);
    }
    return sol;
}

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,r = R,c = C;
    if(n == 2){
        for(int i = 2; i <= c; i++){
            logs[i] = logs[i/2] + 1;
        }
        for(int i = 1; i <= r; i++){
            for(int j = 1; j <= c; j++){
                sp[i][j][0] = W[i][j];
            }
            for(int k = 1; k <= 8; k++){
                for(int j = 1; j+(1<<k)-1 <= c; j++){
                    sp[i][j][k] = min(sp[i][j][k-1],sp[i][j+(1<<k)-1][k-1]);
                }
            }
        }
        for(int i = 1; i <= Q; i++){
            int x1 = X1[i],x2 = X2[i],y1 = Y1[i],y2 = Y2[i];
            int mini = getmin(x1,x2,y1,y2);
            O[i] = mini;
        }
        return;
    }
    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;
        }
    }
}