#include <bits/stdc++.h>
//#include <bits/stdc++.h>
//#define int long long
//using namespace std;
//int n,q,l[200001],b[5000001];
//string s[200001],t[200001];
//signed main(){
////	freopen(".in","r",stdin);
////	freopen(".out","w",stdout);
//	cin >> n >> q;
//	while(q--){
//		cout << "0\n";
//	}
//	return 0;
//}
//#include <bits/stdc++.h>
//#define int long long
//using namespace std;
//int n,q,l[200001],b[5000001];
//string s[200001],t[200001];
//signed main(){
////	freopen(".in","r",stdin);
////	freopen(".out","w",stdout);
//	cin >> n >> q;
//	while(q--){
//		cout << "0\n";
//	}
//	return 0;
//}
//#include <bits/stdc++.h>
//#define int long long
//using namespace std;
//int n,q,l[200001],b[5000001];
//string s[200001],t[200001];
//signed main(){
////	freopen(".in","r",stdin);
////	freopen(".out","w",stdout);
//	cin >> n >> q;
//	while(q--){
//		cout << "0\n";
//	}
//	return 0;
//}
//#include <bits/stdc++.h>
//#define int long long
//using namespace std;
//int n,q,l[200001],b[5000001];
//string s[200001],t[200001];
//signed main(){
////	freopen(".in","r",stdin);
////	freopen(".out","w",stdout);
//	cin >> n >> q;
//	while(q--){
//		cout << "0\n";
//	}
//	return 0;
//}
//#include <bits/stdc++.h>
//#define int long long
//using namespace std;
//int n,q,l[200001],b[5000001];
//string s[200001],t[200001];
//signed main(){
////	freopen(".in","r",stdin);
////	freopen(".out","w",stdout);
//	cin >> n >> q;
//	while(q--){
//		cout << "0\n";
//	}
//	return 0;
//}
//#include <bits/stdc++.h>
//#define int long long
//using namespace std;
//int n,q,l[200001],b[5000001];
//string s[200001],t[200001];
//signed main(){
////	freopen(".in","r",stdin);
////	freopen(".out","w",stdout);
//	cin >> n >> q;
//	while(q--){
//		cout << "0\n";
//	}
//	return 0;
//}
//#include <bits/stdc++.h>
//#define int long long
//using namespace std;
//int n,q,l[200001],b[5000001];
//string s[200001],t[200001];
//signed main(){
////	freopen(".in","r",stdin);
////	freopen(".out","w",stdout);
//	cin >> n >> q;
//	while(q--){
//		cout << "0\n";
//	}
//	return 0;
//}
//#include <bits/stdc++.h>
//#define int long long
//using namespace std;
//int n,q,l[200001],b[5000001];
//string s[200001],t[200001];
//signed main(){
////	freopen(".in","r",stdin);
////	freopen(".out","w",stdout);
//	cin >> n >> q;
//	while(q--){
//		cout << "0\n";
//	}
//	return 0;
//}
//#include <bits/stdc++.h>
//#define int long long
//using namespace std;
//int n,q,l[200001],b[5000001];
//string s[200001],t[200001];
//signed main(){
////	freopen(".in","r",stdin);
////	freopen(".out","w",stdout);
//	cin >> n >> q;
//	while(q--){
//		cout << "0\n";
//	}
//	return 0;
//}
//#include <bits/stdc++.h>
//#define int long long
//using namespace std;
//int n,q,l[200001],b[5000001];
//string s[200001],t[200001];
//signed main(){
////	freopen(".in","r",stdin);
////	freopen(".out","w",stdout);
//	cin >> n >> q;
//	while(q--){
//		cout << "0\n";
//	}
//	return 0;
//}
//#include <bits/stdc++.h>
//#define int long long
//using namespace std;
//int n,q,l[200001],b[5000001];
//string s[200001],t[200001];
//signed main(){
////	freopen(".in","r",stdin);
////	freopen(".out","w",stdout);
//	cin >> n >> q;
//	while(q--){
//		cout << "0\n";
//	}
//	return 0;
//}
//#include <bits/stdc++.h>
//#define int long long
//using namespace std;
//int n,q,l[200001],b[5000001];
//string s[200001],t[200001];
//signed main(){
////	freopen(".in","r",stdin);
////	freopen(".out","w",stdout);
//	cin >> n >> q;
//	while(q--){
//		cout << "0\n";
//	}
//	return 0;
//}
//#include <bits/stdc++.h>
//#define int long long
//using namespace std;
//int n,q,l[200001],b[5000001];
//string s[200001],t[200001];
//signed main(){
////	freopen(".in","r",stdin);
////	freopen(".out","w",stdout);
//	cin >> n >> q;
//	while(q--){
//		cout << "0\n";
//	}
//	return 0;
//}
//#include <bits/stdc++.h>
//#define int long long
//using namespace std;
//int n,q,l[200001],b[5000001];
//string s[200001],t[200001];
//signed main(){
////	freopen(".in","r",stdin);
////	freopen(".out","w",stdout);
//	cin >> n >> q;
//	while(q--){
//		cout << "0\n";
//	}
//	return 0;
//}
//#include <bits/stdc++.h>
//#define int long long
//using namespace std;
//int n,q,l[200001],b[5000001];
//string s[200001],t[200001];
//signed main(){
////	freopen(".in","r",stdin);
////	freopen(".out","w",stdout);
//	cin >> n >> q;
//	while(q--){
//		cout << "0\n";
//	}
//	return 0;
//}
//#include <bits/stdc++.h>
//#define int long long
//using namespace std;
//int n,q,l[200001],b[5000001];
//string s[200001],t[200001];
//signed main(){
////	freopen(".in","r",stdin);
////	freopen(".out","w",stdout);
//	cin >> n >> q;
//	while(q--){
//		cout << "0\n";
//	}
//	return 0;
//}
//#include <bits/stdc++.h>
//#define int long long
//using namespace std;
//int n,q,l[200001],b[5000001];
//string s[200001],t[200001];
//signed main(){
////	freopen(".in","r",stdin);
////	freopen(".out","w",stdout);
//	cin >> n >> q;
//	while(q--){
//		cout << "0\n";
//	}
//	return 0;
//}
//#include <bits/stdc++.h>
//#define int long long
//using namespace std;
//int n,q,l[200001],b[5000001];
//string s[200001],t[200001];
//signed main(){
////	freopen(".in","r",stdin);
////	freopen(".out","w",stdout);
//	cin >> n >> q;
//	while(q--){
//		cout << "0\n";
//	}
//	return 0;
//}
//#include <bits/stdc++.h>
//#define int long long
//using namespace std;
//int n,q,l[200001],b[5000001];
//string s[200001],t[200001];
//signed main(){
////	freopen(".in","r",stdin);
////	freopen(".out","w",stdout);
//	cin >> n >> q;
//	while(q--){
//		cout << "0\n";
//	}
//	return 0;
//}
//#include <bits/stdc++.h>
//#define int long long
//using namespace std;
//int n,q,l[200001],b[5000001];
//string s[200001],t[200001];
//signed main(){
////	freopen(".in","r",stdin);
////	freopen(".out","w",stdout);
//	cin >> n >> q;
//	while(q--){
//		cout << "0\n";
//	}
//	return 0;
//}

#define int long long
using namespace std;
int n,m,k,sum,ans,a[20][10001],qwq2[20],fa[10001],qwq3[1000001][20];
int find(int x)
{
	if(fa[x]==x)return fa[x];
	return fa[x]=find(fa[x]);
}
struct node{
	int u,v,w;
	bool operator < (const node &qwq) const {
		return w<qwq.w;
	}
}qwq1[1000001];
vector<node> qwq4;
signed main(){
	freopen("road.in","r",stdin);
	freopen("road.out","w",stdout);
	cin >> n >> m >> k;
	for(int i=1;i<=m;i++)
	{
		scanf("%lld%lld%lld",&qwq1[i].u,&qwq1[i].v,&qwq1[i].w);
	}
	for(int i=1;i<=k;i++)
	{
		scanf("%lld",&qwq2[i]);
		for(int j=1;j<=n;j++)
		{
			scanf("%lld",&a[i][j]);
		}
	}
	for(int i=1;i<=n;i++)fa[i]=i;
	sort(qwq1+1,qwq1+m+1);
	for(int i=1;i<=m;i++)
	{
		//#include <bits/stdc++.h>
//#define int long long
//using namespace std;
//int n,q,l[200001],b[5000001];
//string s[200001],t[200001];
//signed main(){
////	freopen(".in","r",stdin);
////	freopen(".out","w",stdout);
//	cin >> n >> q;
//	while(q--){
//		cout << "0\n";
//	}
//	return 0;
//}

		int x=find(qwq1[i].u);
		int y=find(qwq1[i].v);
		if(x==y){
			continue;
		}
		sum+=qwq1[i].w;
		fa[x]=y;
		qwq4.push_back(qwq1[i]);
		//#include <bits/stdc++.h>
//#define int long long
//using namespace std;
//int n,q,l[200001],b[5000001];
//string s[200001],t[200001];
//signed main(){
////	freopen(".in","r",stdin);
////	freopen(".out","w",stdout);
//	cin >> n >> q;
//	while(q--){
//		cout << "0\n";
//	}
//	return 0;
//}

	}
	sort(qwq4.begin(),qwq4.end());
	ans=sum;
	
	for(int mm=0;mm<(1<<k);mm++)
	{
		int wcnm=sum;
		for(int i=0;i<k;i++)
		{
			wcnm+=((mm>>i)&1)*qwq2[i+1];
		}
		for(int i=1;i<=n;i++)
		{
			fa[i]=i;
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=k;j++)
			{
				qwq3[i][j]=a[j][i];
			}
		}
		for(auto i:qwq4){
			int x=find(i.u),y=find(i.v);
			if(x==y){
				wcnm-=i.w;
				continue;
			}
			fa[x]=y;
			int mi=2e9+1,id=0;
			for(int j=0;j<=k;j++)
			{
				if((mm>>j)&1)
				{
					if(qwq3[x][j+1]+qwq3[y][j+1]<mi)
					{
						//#include <bits/stdc++.h>
//#define int long long
//using namespace std;
//int n,q,l[200001],b[5000001];
//string s[200001],t[200001];
//signed main(){
////	freopen(".in","r",stdin);
////	freopen(".out","w",stdout);
//	cin >> n >> q;
//	while(q--){
//		cout << "0\n";
//	}
//	return 0;
//}

						mi=qwq3[x][j+1]+qwq3[y][j+1];
						id=j+1;
					}
				}
			}
			for(int j=0;j<k;j++)
			{
				if((mm>>j)&1)
				{
					//#include <bits/stdc++.h>
//#define int long long
//using namespace std;
//int n,q,l[200001],b[5000001];
//string s[200001],t[200001];
//signed main(){
////	freopen(".in","r",stdin);
////	freopen(".out","w",stdout);
//	cin >> n >> q;
//	while(q--){
//		cout << "0\n";
//	}
//	return 0;
//}

					qwq3[y][j+1]=min(qwq3[x][j+1],qwq3[y][j+1]);
				}
			}
			if(mi<=i.w)wcnm=wcnm-i.w+mi,qwq3[y][id]=0;
		}
		ans=min(ans,wcnm);
	}
	printf("%lld",ans);
	return 0;
}
