#include <bits/stdc++.h>
#define pii pair<int,int>
#define f first
#define s second
using namespace std;

struct edge{int a,b,w;};
int cmp(edge A, edge B){return A.w<B.w;}

struct DSU
{
    int f[45];
    void init(){for(int i=0;i<45;i++) f[i]=i;}
    int _find(int x){return x==f[x]?x:f[x]=_find(f[x]);}
    void mrg(int x, int y){f[_find(x)]=_find(y);}
}D;

vector<edge> v;
vector<int> g[45];

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 idi=0;
    if(R<=100 && Q<=100 && C<=100)
    {
        for(int h=1;h<=Q;h++)
        {
            D.init();
            for(int i=1;i<=N;i++) g[i].clear();
            v.clear();
            for(int i=X1[h];i<=X2[h];i++)
            {
                for(int j=Y1[h];j<=Y2[h];j++)
                {
                    int t1=U[i][j];
                    int t2=V[i][j];
                    int t3=W[i][j];
                    edge tmp;
                    tmp.a=t1;
                    tmp.b=t2;
                    tmp.w=t3;
                    v.push_back(tmp);
                }
            }
            sort(v.begin(),v.end(),cmp());
            int res=0;
            for(int i=0;i<v.size();i++)
            {
                int A=v[i].a;
                int B=v[i].B;
                if(D._find(A)!=D._find(B))
                {
                    D.mrg(A,B);
                    res+=v[i].w;
                }
            }
            int ok=1;
            for(int i=1;i<=N;i++) for(int j=1;j<=N;j++)
            {
                if(D._find(i)!=D._find(j)) ok=0;
            }
            if(!ok) O[++idi]=-1;
            else O[++idi]=res;
        }
    }
}