#include <bits/stdc++.h>
#define maxn 53
#define maxr 290
#define inf 1e9
using namespace std;

int p[maxn], ans;
vector<pair<int, pair<int, int> > > es;

int findP(int x){
    if(x == p[x]){
        return p[x];
    }
    return p[x] = findP(p[x]);
}

bool join(int x, int y){
    x = findP(x);
    y = findP(y);
    if(x == y){
        return 0;
    }
    p[x] = y;
    return true;
}

struct segTr{
    int segT[4*maxr];
    void init(int idx, int l, int r, int *a){
        if(!idx){
            for(int i = 0; i < 4*maxr; ++i){
                segT[i] = inf;
            }
        }
        if(l == r){
            segT[idx] = a[l];
            return;
        }
        int mid = (l+r)/2;
        init(idx*2+1, l, mid, a);
        init(idx*2+2, mid+1, r, a);
        segT[idx] = min(segT[idx*2+1], segT[idx*2+2]);
    }
    void update(int idx, int l, int r, int x, int val){
        if(l == r){
            segT[idx] = val;
            return;
        }
        int mid = (l+r)/2;
        if(x <= mid){
            update(idx*2+1, l, mid, x, val);
        } else {
            update(idx*2+2, mid+1, r, x, val);
        }
        segT[idx] = min(segT[idx*2+1], segT[idx*2+2]);
    }
    int getM(int idx, int l, int r, int ql, int qr){
        if(r < ql or l > qr){
            return inf;
        }
        if(r <= qr and l >= ql){
            return segT[idx];
        }
        int mid = (l+r)/2;
        return min(getM(idx*2+1, l, mid, ql, qr), getM(idx*2+2, mid+1, r, ql, qr));
    }
};

struct rSparse{
    int rmq[maxr][10];
    void init(int *a, int n){
        for(int i = 1; i <= n; ++i){
            rmq[i][0] = a[i];
        }
        for(int i = 1; i < 10; ++i){
            for(int j = 1; j <= n; ++j){
                int tmp = (1<<(i-1));
                if(j + tmp > n){
                    rmq[j][i] = rmq[j][i-1];
                    continue;
                }
                rmq[j][i] = min(rmq[j][i-1], rmq[j+tmp][i-1]);
            }
        }
    }
    int getM(int l, int r){
        int res = inf;
        for(int i = 9; i >= 0; --i){
            int nex = l + (1<<i);
            if(nex <= r+1){
                res = min(res, rmq[l][i]);
                l = nex;
            }
        }
        return res;
    }
};

segTr s[maxr];
rSparse s1[maxr], s2[maxr], s3[maxr];
int w1[maxr][maxr], w2[maxr][maxr], w3[maxr][maxr];

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){
    if(N == 3){
        for(int i = 1; i <= R; ++i){
            for(int j = 1; j <= C; ++j){
                w3[i][j] = w2[i][j] = w1[i][j] = inf;
                int u, v;
                // v->u
                u = max(U[i][j], V[i][j]);
                v = min(U[i][j], V[i][j]);
                if(u == 2 and v == 1){
                    w1[i][j] = W[i][j];
                } else if(u == 3 and v == 1){
                    w2[i][j] = W[i][j];
                } else {
                    w3[i][j] = W[i][j];
                }
            }
        }
        for(int i = 1; i <= R; ++i){
            s1[i].init(w1[i], C);
            s2[i].init(w2[i], C);
            s3[i].init(w3[i], C);

        }
        int ans1 = inf, ans2 = inf, ans3 = inf, tmpMax, tmpMin;
        for(int i1 = 1; i1 <= Q; ++i1){
            ans1 = inf;
            ans2 = inf;
            ans3=inf;
            tmpMax = 0;
            tmpMin = inf;
            for(int i = X1[i1]; i <= X2[i1]; ++i){
                ans1 = min(ans1, s1[i].getM(Y1[i1], Y2[i1]));
                ans2 = min(ans2, s2[i].getM(Y1[i1], Y2[i1]));
                ans3 = min(ans3, s3[i].getM(Y1[i1], Y2[i1]));
            }
            tmpMax = max(ans1, max(ans2, ans3));
            tmpMin = min(min(ans1, ans2), ans3);
            int tmp = (ans1+ans2+ans3-tmpMax-tmpMin);
            if(tmp == inf){
                O[i1] = -1;
            } else {
                O[i1] = tmpMin + tmp;
            }
        }
        return;
    }
    if(N == 2){

        for(int i = 1; i <= R; ++i){
            s[i].init(0, 1, C, W[i]);
        }
        for(int i1=1; i1 <= Q; ++i1)
        {
            ans = inf;
            for(int i = X1[i1]; i <= X2[i1]; ++i){
                ans = min(ans, s[i].getM(0, 1, C, Y1[i1], Y2[i1]));
            }
            if(ans != inf)
            {
                O[i1] = ans;
            } else {
                O[i1] = -1;
            }
        }
        return;
    }
    if(Q > 200){
        return;
    }
    for(int i1 = 1; i1 <= Q; ++i1)
    {
        es.clear();
        for(int i = 1; i <= N; ++i){
            p[i] = i;
        }
        ans = 0;
        for(int i = X1[i1]; i <= X2[i1]; ++i){
            for(int j = Y1[i1]; j <= Y2[i1]; ++j){
                es.push_back({W[i][j], {U[i][j], V[i][j]}});
            }
        }
        sort(es.begin(), es.end());
        for(auto i : es){
            int u = i.second.first, v = i.second.second;
            // u -> v
            if(join(u, v)){
                ans += i.first;
            }
        }
        int minP = maxn, maxP = 0;
        for(int i = 1 ; i <= N; ++i){
            maxP = max(maxP, findP(i));
            minP = min(minP, findP(i));
        }
        if(maxP == minP){
            O[i1] = ans;
        } else {
            O[i1] = -1;
        }
    }
};