#include <iostream>
using namespace std;

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);

static int** matrica(int R, int C) {
	int** a = new int*[R+1];
	for (int i=1; i<=R; i++)
		a[i] = new int[C+1];
	return a;
}

static void pocisti(int** a, int R) {
	for (int i=1; i<=R; i++)
		delete[] a[i];
	delete a;
}


#include<bits/stdc++.h>
#define maxn 255
#define pii pair<int,int>
using namespace std;

int sz[45];
int p[45];
int adj[45][45];

vector<pair<int,pii>>g;

void build(int n)
{
    for(int i=1;i<=n;i++)
    {
        sz[i]=1;
        p[i]=i;
    }
}
int fnd(int x)
{
    if(x==p[x])return x;
    return p[x]=fnd(p[x]);
}
bool same(int x,int y)
{
    return fnd(x)==fnd(y);
}
void unite(int x,int y)
{
    x=fnd(x);
    y=fnd(y);
    if(sz[x]<sz[y])swap(x,y);
    sz[x]+=sz[y];
    p[y]=x;
}


int minn[maxn][maxn][10][10];
//int g1[maxn][maxn];
void build2(int r,int c,int** g1)
{
    int dr=log2(r);
    int dc=log2(c);
    for(int dx=0;dx<=dr;dx++)
        for(int dy=0;dy<=dc;dy++)
        {
            for(int x=1;x+(1<<dx)-1<=r;x++)
            {
                for(int y=1;y+(1<<dy)-1<=c;y++)
                {
                    if(dx==0 && dy==0)
                    {
                        minn[x][y][dx][dy]=g1[x][y];
                    }
                    else if(dx!=0)
                    {
                        minn[x][y][dx][dy]=min(minn[x][y][dx-1][dy],minn[x+(1<<(dx-1))][y][dx-1][dy]);
                    }
                    else
                    {
                        minn[x][y][dx][dy]=min(minn[x][y][dx][dy-1],minn[x][y+(1<<(dy-1))][dx][dy-1]);
                    }
                }
            }
        }
}
int minnn(int x1,int y1,int x2,int y2)
{
    if(x1>x2)swap(x1,x2);
    if(y1>y2)swap(y1,y2);

    int lx=log2(x2-x1+1);
    int ly=log2(y2-y1+1);

    return min(min(minn[x1][y1][lx][ly],minn[x2-(1<<lx)+1][y1][lx][ly]),min(minn[x1][y2-(1<<ly)+1][lx][ly],minn[x2-(1<<lx)+1][y2-(1<<ly)+1][lx][ly]));
}


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>2)
    {
    for(int br=1;br<=q;br++)
    {
        if(x1[br]>x2[br])swap(x1[br],x2[br]);
        if(y1[br]>y2[br])swap(y1[br],y2[br]);
        for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)adj[i][j]=-1;
        for(int i=x1[br];i<=x2[br];i++)
        {
            for(int j=y1[br];j<=y2[br];j++)
            {
                int uu=u[i][j];
                int vv=v[i][j];
                if(uu>vv)swap(uu,vv);
                int ww=w[i][j];
                if(adj[uu][vv]==-1 || adj[uu][vv]>ww)
                {
                    adj[uu][vv]=ww;
                }
            }
        }

        g.clear();
        for(int i=1;i<=n;i++)
        {
            for(int j=i+1;j<=n;j++)
            {
                if(adj[i][j]!=-1)
                {
                    g.push_back({adj[i][j],{i,j}});
                }
            }
        }

        sort(g.begin(),g.end());
        /*cout<<br<<endl;
        for(auto x:g)cout<<x.first<<" "<<x.second.first<<","<<x.second.second<<endl;
        cout<<endl<<endl;*/

        build(n);
        o[br]=0;
        int cv=1;
        int len=g.size();
        for(int i=0;i<len;i++)
        {
            int uu=g[i].second.first;
            int vv=g[i].second.second;
            int ww=g[i].first;
            if(!same(uu,vv))
            {
                o[br]+=ww;
                cv++;
                unite(uu,vv);
            }
        }

        if(cv<n)o[br]=-1;
    }
    }

    else
    {
        build2(r,c,w);
        /*for(int i=1;i<=r;i++)
        {
            for(int j=1;j<=c;j++)
            {
                for(int k=0;i+(1<<k)-1<=r;k++)cout<<minn[i][j][k][0]<<" ";
                cout<<"    ";
            }
            cout<<endl;
        }

        cout<<endl<<endl;*/
        for(int i=1;i<=q;i++)
        {
            o[i]=minnn(x1[i],y1[i],x2[i],y2[i]);
        }
    }
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int N, R, C, Q;
	cin >> N >> R >> C >> Q;

	int** U = matrica(R, C);
	int** V = matrica(R, C);
	int** W = matrica(R, C);

	int* X1 = new int[Q+1];
	int* Y1 = new int[Q+1];
	int* X2 = new int[Q+1];
	int* Y2 = new int[Q+1];
	int* O  = new int[Q+1];

	for (int i=1; i<=R; i++)
		for (int j=1; j<=C; j++)
			cin >> U[i][j] >> V[i][j] >> W[i][j];

	for (int i=1; i<=Q; i++)
		cin >> X1[i] >> Y1[i] >> X2[i] >> Y2[i];

	Resi(N, R, C, Q, U, V, W, X1, Y1, X2, Y2, O);

	for (int i=1; i<=Q; i++)
		cout << O[i] << '\n';

	delete[] X1;
	delete[] Y1;
	delete[] X2;
	delete[] Y2;
	delete[] O;

	pocisti(U, R);
	pocisti(V, R);
	pocisti(W, R);
}
/*
4
2 3 4 3
1 2 1  1 2 2  1 2 3  1 2 100
2 3 2  2 3 3  2 3 1  2 3 101
3 4 3  3 4 1  3 4 2  3 4 102
1 1 3 4
1 2 3 3
3 4 3 4
*/