WA64pts求条

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e4+15;
const int M=2e6+5;
struct Edge
{
	int x,y,w;
	bool operator<(const Edge &a) {return w<a.w;}
}edge[M],e[N];
int n,m,k;
int c[13][N];
int fa[N],sz[N];
int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);}
signed main()
{
	scanf("%lld%lld%lld",&n,&m,&k);
	for(int i=1;i<=m;++i) scanf("%lld%lld%lld",&edge[i].x,&edge[i].y,&edge[i].w);
	for(int i=1;i<=k;++i)
		for(int j=0;j<=n;++j) scanf("%lld",&c[i][j]);
	sort(edge+1,edge+m+1);
	for(int i=1;i<=n;++i) fa[i]=i,sz[i]=1;
	int cnt=0;
	for(int i=1;i<=m&&cnt<n-1;++i)
	{
		int x=find(edge[i].x),y=find(edge[i].y);
		if(x==y) continue;
		if(sz[x]<sz[y]) swap(x,y);
		sz[x]+=sz[y],fa[y]=x,e[++cnt]=edge[i];
	}
	for(int i=1;i<=k;++i)
		for(int j=1;j<=n;++j)
			e[++cnt]={j,n+i,c[i][j]};
	sort(e+1,e+cnt+1);
	int ans=4e18;
	for(int i=0;i<(1<<k);++i)
	{
		int ansx=0,ct=0,p=n;
		for(int j=1;j<=k;++j)
			if((i>>j-1)&1) ansx+=c[j][0],p++;
		for(int j=1;j<=p;++j) fa[j]=j,sz[j]=1;
		for(int j=1;j<=cnt&&ct<p-1;++j)
		{
			int x=e[j].x,y=e[j].y;
			if(x>n&&!((i>>x-n-1)&1)||y>n&&!((i>>y-n-1)&1)) continue;
			x=find(x),y=find(y);
			if(x==y) continue;
			if(sz[x]<sz[y]) swap(x,y);
			sz[x]+=sz[y],fa[y]=x,ansx+=e[j].w,ct++;
		}
		ans=min(ans,ansx);
	}
	printf("%lld\n",ans);
	return 0;
}