#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#define lld long long
#define pb push_back
#define ff first
#define ss second
using namespace std;
const int maxr=250;
const int maxn=40;
const int maxq=2e5;
int n,par[maxn+10],cc,q,r,c,br,rez[maxq+10];
struct point{
   int x,y;
};
struct ss{
   point gl,dd;
   int id;
}qq[maxq+10];
struct ed{
   int u,v,w;
}edge[maxr+10][maxr+10],stek[maxr*maxr+10];

void reset_dsu(){
   for(int i=1;i<=n;i++)
    par[i]=i;
}
bool srt(ed a,ed b){
   return a.w<b.w;
}
int root(int x){
   if(x==par[x])return x;
   return par[x]=root(par[x]);
}
bool unite(int x,int y){
   int xroot=root(x);
   int yroot=root(y);
   if(xroot==yroot)return 0;
   cc--;
   par[xroot]=yroot;
}
void brute(){

   for(int i=1;i<=q;i++){

      int ll=qq[i].gl.y;
      int rr=qq[i].dd.y;

      int up=qq[i].gl.x;
      int down=qq[i].dd.x;

      br=0;
      for(int kk=up;kk<=down;kk++)
        for(int j=ll;j<=rr;j++)
           stek[++br]=edge[kk][j];


      reset_dsu();
      sort(stek+1,stek+br+1,srt);
      cc=n;

      for(int j=1;j<=br;j++){
        if(unite(stek[j].u,stek[j].v))rez[qq[i].id]+=stek[j].w;
      }

      if(cc>1)rez[qq[i].id]=-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=1; i<=Q; i++)
		O[i] = -1;

    q=Q;
    c=C;
    n=N;
    r=R;

    for(int i=1;i<=q;i++){
        qq[i].gl.x=X1[i];
        qq[i].gl.y=Y1[i];
        qq[i].dd.x=X2[i];
        qq[i].dd.y=Y2[i];
        qq[i].id=i;
    }

    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++)
            edge[i][j]={min(U[i][j],V[i][j]),max(U[i][j],V[i][j]),W[i][j]};


    if(q<=100)brute();

    for(int i=1;i<=q;i++)O[i]=rez[i];

}