【玄关】求调/Hack 96pts

//Author: mairuisheng
//#pragma GCC optimize(3)
#include<iostream>
#include<vector>
#include<algorithm>
#define int long long
using namespace std;
inline int read()
{
	int x=0,f=1;
	char s;
	s=getchar();
	while(s<48||s>57)
	{
		if(s=='-')f=-f;
		s=getchar();
	}
	while(s>47&&s<58)
	{
		x=(x<<3)+(x<<1)+s-48;
		s=getchar();
	}
	return x*f;
}
constexpr int N=1e4+21,K=11,M=2e6+1,KN=110005,MAX=2e18;
struct Edge
{
	int xx,yy,val;
}ed[M],ned[KN];
int n,m,k;
int c[K],a[K][N],f[N+K],cho[N],num[N+K];
int ans;
bool Cmp(Edge x,Edge y)
{
	return x.val<y.val;
}
int Find(int x)
{
	return x==f[x]?x:f[x]=Find(f[x]);
}
int Work1()
{
	int i,tot=0,fx,fy,res=0;
	for(i=1;i<=n;++i)f[i]=i;
	sort(ed+1,ed+1+m,Cmp);
	for(i=1;i<=m;++i)
	{
		fx=Find(ed[i].xx);
		fy=Find(ed[i].yy);
		if(fx!=fy)
		{
			f[fx]=fy;
			cho[++tot]=i;
			res+=ed[i].val;
			if(tot==n-1)return res;
		}
	}
}
int Work2(int w)
{
	int i,tot=0,fx,fy,res=0,u;
	for(i=1;i<=n+k;++i)
	{
		f[i]=i;
		num[i]=i>n?1:0;
	}
	for(i=1;i<=m;++i)
	{
		if(ned[i].xx>n)
		{
			u=ned[i].xx-n-1;
			if((w>>u&1)==0)continue;
		}
		if(ned[i].yy>n)
		{
			u=ned[i].yy-n-1;
			if((w>>u&1)==0)continue;
		}
		fx=Find(ned[i].xx);
		fy=Find(ned[i].yy);
		if(fx!=fy)
		{
			f[fx]=fy;
			num[fy]+=num[fx];
			res+=ned[i].val;
			if(res>=ans)return MAX;
			++tot;
			if(tot-num[fy]>=n-1)return res;
		}
	}
}
signed main()
{
	n=read();
	m=read();
	k=read();
	int i,u,v,w,j,lim=1<<k;
	for(i=1;i<=m;++i)
	{
		u=read();
		v=read();
		w=read();
		ed[i]={u,v,w};
	}
	for(i=1;i<=k;++i)
	{
		c[i]=read();
		for(j=1;j<=n;++j)a[i][j]=read();
	}
	ans=Work1();
	for(i=1;i<n;++i)ned[i]=ed[cho[i]];
	m=n-1;
	for(i=1;i<=k;++i)
	{
		for(j=1;j<=n;++j)
		{
			++m;
			ned[m]={i+n,j,a[i][j]};
		}
	}
	sort(ned+1,ned+1+m,Cmp);
	for(i=1;i<lim;++i)
	{
		w=i;
		u=v=0;
		while(w)
		{
			++u;
			if(w&1)v+=c[u];
			w>>=1;
		}
		ans=min(ans,Work2(i)+v);
	}
	printf("%lld",ans);
	return 0;
}