#include <bits/stdc++.h>
#define maxN 44

using namespace std;

vector< pair<int,int> > adj[maxN];
int g[maxN][maxN],i,j,k,n;

void funk(){
int i,j;
for(i=1;i<=n;i++){
    adj[i].clear();
    for(j=1;j<=n;j++){
        g[i][j]=1000000000;
    }
}
}

void funk2(){
int i,j;
for(i=1;i<=n;i++){
    for(j=1;j<=n;j++){
        if(g[i][j]!=1000000000){
            adj[i].push_back({j,g[i][j]});
            //cout<<"!"<<i<<" "<<j<<" "<<g[i][j]<<endl;
        }
    }
}
}

int mcst(int n){
int cnt=1,i,x,res=0;
int mar[maxN],dis[maxN];
priority_queue < pair<int,int> > pq;
pq.push({0,1});
for(i=2;i<=n;i++) {mar[i]=false; dis[i]=1000000000;}
dis[1]=0;
mar[1]=false;
while(pq.size()){
    x=pq.top().second;
    if(!mar[x]) res-=pq.top().first;
    pq.pop();
    if(mar[x]) continue;
    //cout<<x<<" "<<res<<endl;
    mar[x]=true;
    cnt++;
    for(i=0;i<adj[x].size();i++){
        if(adj[x][i].second<dis[adj[x][i].first]){
            dis[adj[x][i].first]=adj[x][i].second;
            pq.push({-dis[adj[x][i].first],adj[x][i].first});
        }
    }
}
if(cnt<n) return -1;
return res;
}

//int u[maxN][maxN],v[maxN][maxN],w[maxN][maxN];

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){
n=N;
if(Q>100) return;
for(int i=1;i<=Q;i++){
    funk();
    for(j=x1[i];j<=x2[i];j++){
        for(k=y1[i];k<=y2[i];k++){
            //cout<<j<<" "<<k<<" "<<u[j][k]<<" "<<v[j][k]<<endl;
            g[u[j][k]][v[j][k]]=min(g[u[j][k]][v[j][k]],w[j][k]);
            g[v[j][k]][u[j][k]]=min(g[v[j][k]][u[j][k]],w[j][k]);
        }
    }
    funk2();
    o[i]=mcst(n);
}
}