80pts求调

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6+1,M=1e4+11;
struct node{ll st,to,wg;}edge[N+N/5+1];
ll n,m,k,U,V,W,fa[M],ans,u[M],v[M],w[M],cnt,costt[11][M];
bool cmp(node x,node y){return x.wg<y.wg;}
ll find(ll x){
	if (fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
void merge(ll x,ll y){fa[find(x)]=find(y);}
int main(){
	cin>>n>>m>>k;
	for (ll i=1;i<=M;i++) fa[i]=i;
	for (ll i=1;i<=m;i++){
		cin>>U>>V>>W;
		edge[i].st=U;
		edge[i].to=V;
		edge[i].wg=W;
	}
	for (ll i=1;i<=k;i++) for (ll j=0;j<=n;j++) cin>>costt[i][j];
	ans=0; 
	sort(edge+1,edge+m+1,cmp);
	for (ll i=1;i<=m;i++){
		ll x=edge[i].st,y=edge[i].to,z=edge[i].wg;
		if (find(x)!=find(y)){
			merge(x,y);
			ans+=z;
			u[++cnt]=x;
			v[cnt]=y;
			w[cnt]=z;
		}
	}
	ll res=ans; 
	for (ll i=1;i<(1<<k);i++){
		ll j=i,l=k,st[20],cost=0,flag=1,count=cnt,cntt=0;
		for (ll a=1;a<=cnt;a++){
			edge[a].st=u[a];
			edge[a].to=v[a];
			edge[a].wg=w[a];
		}
		memset(st,0,sizeof(st));
		for (ll a=1;a<=M;a++) fa[a]=a;
		while (j){
			st[l]=j%2;
			l--;
			j/=2;
		}
		for (ll a=1;a<=k;a++)
		if (st[a]==1){
			cntt++;
			cost+=costt[a][0];
			if (cost>=ans){
				flag=0;
				break;
			}
			for (ll cont=1;cont<=n;cont++){
				edge[++count].st=cntt+n;
				edge[count].to=cont;
				edge[count].wg=costt[a][cont];
			}
		}
		if (flag==0) continue;
		sort(edge+1,edge+count+1,cmp);
		for (ll a=1;a<=count;a++){
			ll x=edge[a].st,y=edge[a].to,z=edge[a].wg;
			if (find(x)!=find(y)){
				merge(x,y);
				cost+=z;
			}
		}
		res=min(cost,res);
	}
	cout<<res;
}