#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=0,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];

int a[4][4][255][255],seg[4][4][255][4*255];

void build(int p,int b,int c,int n,int l,int d){
if(l==d){
    seg[p][b][c][n]=a[p][b][c][l];
    return;
}
int m=(l+d)/2;
build(p,b,c,2*n,l,m);
build(p,b,c,2*n+1,m+1,d);
seg[p][b][c][n]=min(seg[p][b][c][2*n],seg[p][b][c][2*n+1]);
}

int query(int p,int b,int c,int n,int l,int d,int x,int y){
if(l>y || d<x) return 1000000000;
if(l>=x && d<=y) return seg[p][b][c][n];
int m=(l+d)/2;
return min(query(p,b,c,2*n,l,m,x,y),query(p,b,c,2*n+1,m+1,d,x,y));
}

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 && n>3) return;
if(n<=3){
for(i=1;i<=R;i++){
    for(j=1;j<=C;j++){
        a[u[i][j]][v[i][j]][i][j]=w[i][j];
    }
}
for(i=1;i<=n;i++){
    for(j=1;j<=n;j++){
        for(k=1;k<=R;k++) build(i,j,k,1,0,C);
    }
}
for(int i=1;i<=Q;i++){
    funk();
    for(j=x1[i];j<=x2[i];j++){
        for(k=1;k<=n;k++){
            for(int t=1;t<=n;t++){
                g[k][t]=min(g[k][t],query(k,t,j,1,0,C,y1[i],y2[i]));
                g[t][k]=min(g[t][k],g[k][t]);
            }
        }
    }
    funk2();
    o[i]=mcst(n);
}
}
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);
}
}