#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N(1e5+10);
int n,ans(0);
struct node{
	int a,b,c;
	int maxx,next;
}e[N];
vector<int>x,y,z,sc;
void solve(){
	cin>>n;
	ans=0;
	x.clear();y.clear();
	z.clear();sc.clear();
	for(int i(1);i<=n;i++){
		cin>>e[i].a>>e[i].b>>e[i].c;
		e[i].maxx=max(e[i].a,max(e[i].b,e[i].c));
		ans+=e[i].maxx;
		if(e[i].maxx==e[i].a){
			x.push_back(i);
			e[i].next=max(e[i].b,e[i].c);
		}
		if(e[i].maxx==e[i].b){
			y.push_back(i);
			e[i].next=max(e[i].a,e[i].c);
		}
		if(e[i].maxx==e[i].c){
			z.push_back(i);
			e[i].next=max(e[i].b,e[i].a);
		}
	}
	int siz(max(x.size(),max(y.size(),z.size())));
	if(siz>n/2){
		if(siz==x.size()){
			for(int i(0);i<siz;i++){
				sc.push_back(e[x[i]].maxx-e[x[i]].next);
			}
		}
		if(siz==y.size()){
			for(int i(0);i<siz;i++){
				sc.push_back(e[y[i]].maxx-e[y[i]].next);
			}
		}
		if(siz==z.size()){
			for(int i(0);i<siz;i++){
				sc.push_back(e[z[i]].maxx-e[z[i]].next);
			}
		}
	}
	sort(sc.begin(),sc.end());
	for(int i(0);sc.size()>n/2&&i<sc.size()-n/2;i++){
		ans-=sc[i];
	}
	cout<<ans<<'\n';
}
int main(){
	int T;
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N(1e5+10);
ll n,m,k;
ll ans(1e18+7);
ll f[N],cost[15];
bool vis[15];
struct node{
	ll u,v,w;
};
vector<node>e,ee;
ll find(ll x){
	if(f[x]==x){
		return x;
	}
	return f[x]=find(f[x]);
}
bool cmp(node a,node b){
	return a.w<b.w;
}
int main(){
	cin>>n>>m>>k;
	// cout<<n<<'\n';
	for(ll i(1);i<=n;i++){
		f[i]=i;
	}
	for(ll i(1);i<=m;i++){
		ll u,v,w;
		cin>>u>>v>>w;
		ee.push_back({u,v,w});
	}
	sort(ee.begin(),ee.end(),cmp);
	ll tot(0);
	for(ll i(1);i<=m&&tot!=n-1;i++){
		ll u(find(ee[i].u)),v(find(ee[i].v));
		if(u!=v){
			f[v]=u;
			tot++;
			e.push_back(ee[i]);
		}
	}
	for(ll i(1);i<=k;i++){
		ll c;
		cin>>c;
		cost[i]=c;
		for(ll j(1);j<=n;j++){
			ll w;
			cin>>w;
			e.push_back({j,n+i,w});
		}
	}
	sort(e.begin(),e.end(),cmp);
	for(ll stat(0);stat<(1<<k);stat++){
		ll now(0);
		ll num(0);
		for(ll i(1);i<=k;i++){
			if((stat>>(i-1))&1){
				num++;
				vis[i]=true;
				now+=cost[i];
			}else{
				vis[i]=false;
			}
		}
		for(ll i(1);i<=n+k;i++){
			f[i]=i;
		}
		ll need(n+num-1);
		for(ll i(0);i<e.size();i++){
			ll u(e[i].u),v(e[i].v);
			if(v>n&&!vis[v-n]){
				continue;
			}
			ll fu(find(u)),fv(find(v));
			if(fu!=fv){
				f[fv]=fu;
				now+=e[i].w;
				if(!(--need)){
					break;
				}
			}
		}
		if(!need){
			ans=min(ans,now);
		}
	}
	cout<<ans<<'\n';
	return 0;
}