#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = (int)(l); i <= (int)(r); i++)
#define per(i, l, r) for (int i = (int)(r); i >= (int)(l); i--)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
using i64 = long long;
#define int i64
const int maxn = 10050, mod = 998244353;
int n, m, k;
int a[12][maxn], c[20];
vector<pair<int, int>> e[maxn], e1[maxn];
int vis[maxn];
void Pr() {
	rep(i, 1, n) {
		vis[i] = 0;
	}
	priority_queue<pair<int, pair<int, int>>> q;
	q.push({0, {1, 0}});
	int res = 0, cnt = 0;
	while (q.size()) {
		pair<int, pair<int, int>> u = q.top();
		if (vis[u.second.first]) {
			q.pop();
			continue;
		}
		cnt++;
		if (u.second.first != 1) {
			e[u.second.first].push_back({u.second.second, -u.first});
			e[u.second.second].push_back({u.second.first, -u.first});
//			cout << u.second.first << " " << u.second.second << " " << -u.first << "\n";
		}
		if (cnt == n) {
			return;
		}
		q.pop();
		vis[u.second.first] = 1;
		for (pair<int, int> _ : e1[u.second.first]) {
			int v = _.first, w = _.second;
			q.push({-w, {v, u.second.first}});
		}
	}
} 
int Prim(int p) {//�Ե�ǰͼ����С������ 
	rep(i, 1, n + k) {
		vis[i] = 0;
	}
	priority_queue<pair<int, int>> q;
	q.push({0, 1});
	int res = 0, cnt = 0;
	while (q.size()) {
		int u = q.top().second;
		if (vis[u]) {
			q.pop();
			continue;
		}
		cnt++;
		res -= q.top().first;
		if (cnt == n + p) {
			return res;
		}
		q.pop();
		vis[u] = 1;
		for (pair<int, int> _ : e[u]) {
			int v = _.first, w = _.second;
			q.push({-w, v});
		}
	}
	return 1e17;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	freopen("road.in", "r", stdin);
	freopen("road.out", "w", stdout);

	cin >> n >> m >> k;
	rep(i, 1, m) {
		int u, v, w;
		cin >> u >> v >> w;
		e1[u].push_back({v, w});
		e1[v].push_back({u, w});
	}
	Pr(); 
	rep(i, 1, k) {
		cin >> c[i];
		rep(j, 1, n) {
			cin >> a[i][j];
		}
	}
	int ans = 1e17;
	rep(S, 0, (1 << k) - 1) {
		int now = 0, q = 0;
		rep(i, 1, k) {
			if (S & (1 << (i - 1))) {
				q++;
				rep(j, 1, n) {
					e[n + i].push_back({j, a[i][j]});
					e[j].push_back({n + i, a[i][j]});
				}
				now += c[i];
			}
		}
		int P = Prim(q);
		now += P;
		ans = min(ans, now);
		rep(i, 1, k) {
			if (S & (1 << (i - 1))) {
				rep(j, 1, n) {
					e[j].pop_back();
					e[n + i].pop_back();
				}
			}
		}
	}
	cout << ans << "\n";
	return 0;
} 
//T2
//����һ������С��������������ö�ټ���ĵ�ı�ţ�2^10��Ȼ���൱������������һ�������������һЩ��Ȼ����prim 
//ʱ�临�Ӷ��Ǵ�� O(2^10*nlogm)���õ�������ֻ��B�㷨�ˣ�����ʵ��д���������������˰� 
//���Բ��ԣ���������ԭͼ���ܳ���С��������Ȼ������������Ȼ��Ͷ����� 

