#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;
const int cst=512;
int n,par[maxn+10],cc,q,r,c,br,rez[maxq+10],inf=1e9;
int tree12[2*cst+10][2*cst+10],tree13[2*cst+10][2*cst+10],tree23[2*cst+10][2*cst+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 update_last(int x,int l,int r,int u,int v,int row,int y){

   if(l==r){
      if(edge[row][l].u==u && edge[row][l].v==v){
        if(u==1 && v==2)tree12[y][x]=edge[row][l].w;
        else if(u==1 && v==3)tree13[y][x]=edge[row][l].w;
        else if(u==2 && v==3)tree23[y][x]=edge[row][l].w;
      }
      return;
   }
   int mid=(l+r)/2;
   update_last(x*2,l,mid,u,v,row,y);
   update_last(x*2+1,mid+1,r,u,v,row,y);

    if(u==1 && v==2)tree12[y][x]=min(tree12[y][x*2],tree12[y][x*2+1]);
    else if(u==1 && v==3)tree13[y][x]=min(tree13[y][x*2],tree13[y][x*2+1]);
    else if(u==2 && v==3)tree23[y][x]=min(tree23[y][x*2],tree23[y][x*2+1]);
}
void update(int x,int l,int r,int u,int v,int y){

    if(u==1 && v==2)tree12[y][x]=min(tree12[y*2][x],tree12[y*2+1][x]);
    else if(u==1 && v==3)tree13[y][x]=min(tree13[y*2][x],tree13[y*2+1][x]);
    else if(u==2 && v==3)tree23[y][x]=min(tree23[y*2][x],tree23[y*2+1][x]);

    if(l==r)return;
    int mid=(l+r)/2;
    update(x*2,l,mid,u,v,y);
    update(x*2+1,mid+1,r,u,v,y);
}
void build(int x,int l,int r,int u,int v){

   if(l==r){
    update_last(1,1,c,u,v,x,l);
    return;
   }
   update(1,1,c,u,v,x);

   int mid=(l+r)/2;
   build(x*2,l,mid,u,v);
   build(x*2+1,mid+1,r,u,v);
}
int query2(int x,int l,int r,int ll,int rr,int u,int v,int y){
   if(l>rr || r<ll)return inf;
   if(l>=ll && r<=rr){
    if(u==1 && v==2)return tree12[y][x];
    else if(u==1 && v==3)return tree13[y][x];
    else if(u==2 && v==3)return tree23[y][x];
   }
   int mid=(l+r)/2;
   return min(query2(x*2,l,mid,ll,rr,u,v,y),query2(x*2+1,mid+1,r,ll,rr,u,v,y));
}
int query(int x,int l,int r,int ll,int rr,int yl,int yr,int u,int v){
   if(l>rr || r<ll)return inf;
   if(l>=ll && r<=rr)return query2(1,1,c,yl,yr,u,v,x);
   int mid=(l+r)/2;
   return min(query(x*2,l,mid,ll,rr,yl,yr,u,v),query(x*2+1,mid+1,r,ll,rr,yl,yr,u,v));
}
void go(){

   for(int i=1;i<=2*cst;i++)
    for(int j=1;j<=2*cst;j++){
      tree12[i][j]=inf;
      tree13[i][j]=inf;
      tree23[i][j]=inf;
    }

   if(n>2)build(1,1,r,1,3);
   build(1,1,r,1,2);
   if(n>2)build(1,1,r,2,3);


   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;

      if(n==2){
        int pom=query(1,1,r,up,down,ll,rr,1,2);
        if(pom==inf)rez[qq[i].id]=-1;
        else rez[qq[i].id]=pom;
      }

   }

}

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();
    else if(n<=3)*/go();

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

}