16pts求条

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,k,fa[1000000],ans=0,cnt,a[20][20000],vis[20000],lzq;
struct node{
	int u,v,w,id;
}g[1000000],v[1000000];
int find(int x){
	if(x==fa[x]) return x;
	return fa[x]=find(fa[x]);
}
bool cmp(node s1,node s2){
	return s1.w<s2.w;
}
signed main(){
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++){
		cin>>g[i].u>>g[i].v>>g[i].w;
	}
	sort(g+1,g+1+m,cmp);
	for(int i=1;i<=n;i++){
		fa[i]=i;
	}
	for(int i=1;i<=m;i++){
		int x=find(g[i].u),y=find(g[i].v);
		if(x==y) continue;
		else{
			v[++cnt]={g[i].u,g[i].v,g[i].w,cnt};
			fa[x]=y;
			ans+=g[i].w;
		}
	}
	for(int i=1;i<=k;i++){
		cin>>a[i][0]; 
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
			v[++cnt]={n+i,j,a[i][j],cnt};
		}
	}
	sort(v+1,v+1+cnt,cmp);
	for(int i=0;i<(1<<k);i++){
		int cnt=0,sum=0;
		for(int i=n+1;i<=n+k;i++){
			if((1<<(i-n-1))&1){
				fa[i]=i;
				cnt++;
				sum+=a[i-n][0],vis[i-n]=1;
			}
			else vis[i]=0;
		} 
		for(int i=1;i<=n;i++) fa[i]=i;
		for(int i=1;i<=n-1+k*n;i++){
			if(i<=n-1||vis[(v[i].id+n-1)/n]){
				int x=find(v[i].u),y=find(v[i].v);
				if(x==y) continue;
				else{
					sum+=v[i].w;
					fa[x]=y;
				}
			}
		}
		ans=min(ans,sum);
	}
	cout<<ans;
	return 0;
}