#include <algorithm>
#include <unordered_map>
//#include <iostream>

using namespace std;

struct Grana
{
    int W;
    int S;
    int E;
    int ID;
};

Grana Grane[62507];
int UF[256];
unordered_map<int,bool> Avail;

bool Grana_comp(Grana a,Grana b)
{
    return a.W < b.W;
}

void setAvail(int X1,int Y1,int X2, int Y2,int C)
{
    --X1;
    --X2;
    --Y1;
    --Y2;
    Avail.clear();
    for(int i=X1;i<=X2;i++)
    {
        for(int j=Y1;j<=Y2;j++)
        {
            Avail[i*C+j]=true;
        }
    }
}

void ResetUF(int N)
{
    for(int i=0;i<N;i++)
    {
        UF[i]=i;
    }
}

int UFF(int a)
{
    int t = UF[a];
    while(t!=a)
    {
        a=t;
        t= UF[a];
    }

    return a;
}

void UFU(int a,int b)
{
    UF[UFF(a)]=UFF(b);
}

int SpecK(int N,int C,int R)
{
    int br=0;
    int sumcost=0;
    int poi=0;
    while(br<N-1 && poi<(C*R))
    {
//        cout<<"Checking: "<<Grane[poi].S<<" "<<Grane[poi].E<<" "<<Grane[poi].W<<" ";
        if(UFF(Grane[poi].S)!=UFF(Grane[poi].E) && Avail[Grane[poi].ID]==true)
        {
//            cout<<"OK";
            sumcost+=Grane[poi].W;
            UFU(Grane[poi].S,Grane[poi].E);
            br++;
        }
//        cout<<endl;
        poi++;
    }
    if(br==N-1){return sumcost;}else{return -1;}
}

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)
{
    for(int i=0;i<R;i++)
    {
        for(int j=0;j<C;j++)
        {
            Grane[i*C+j].W=W[i+1][j+1];
            Grane[i*C+j].S=U[i+1][j+1];
            Grane[i*C+j].E=V[i+1][j+1];
            Grane[i*C+j].ID=i*C+j;
        }
    }

    sort(Grane,Grane+(R*C),Grana_comp);

	for (int i=1; i<=Q; i++)
    {
        setAvail(X1[i],Y1[i],X2[i],Y2[i],C);
//        for(int i1=0;i1<R;i1++)
//        {
//            for(int j1=0;j1<C;j1++)
//            {
//                cout<<Avail[i1*C+j1]<<" ";
//            }
//            cout<<endl;
//        }
        ResetUF(N);
        O[i] = SpecK(N,C,R);
//        cout<<endl;
    }
}