// author: M@
#define m_
//#define _DEBUG_
#include<iostream>
#include<cstdio>
#include<string.h>
#include<iomanip>
#include<queue>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
#include<list>
#include<set>
#include<string>
#define clr(a)   memset((a),0,sizeof (a))
//#define li idx<<1
//#define ri idx<<1|1

using namespace std;
typedef unsigned int ui;
typedef long long LL;
typedef pair<int,int> pii;
//const int INF=0x3f3f3f3f;
const int INF = 1e9 + 7;
const LL LINF=1e18;
const double DINF=1e9;
const double EPS=1e-9;
const int maxn= 1e2 + 5;
const int maxm = 13;
const int mod = 1000000007;
int n, m, k;
int need[maxn][maxm];
int dp[1 << maxm][maxm];
int A[maxn][maxm];

struct edg{
	int to, nxt, w;
}e[maxn * 2];
int head[maxn], cnt;
int tall[maxn];


void add_edg(int fx, int x, int w){
	e[++cnt] = {x, head[fx], w};
	head[fx] = cnt;
}

int dfs(int idx, int knd, int dep, int fa){
	int ret = 0;
	tall[idx] = need[idx][knd] ? dep : 0;
	for(int i = head[idx]; i; i = e[i].nxt){
		int to = e[i].to;
		if(fa == to) continue;
		int temp = dfs(to, knd, dep + e[i].w, idx);
		if(tall[to]){
			ret += 2 * e[i].w + temp;
			tall[idx] = max(tall[idx], tall[to]);
		}
	}
	return ret;
}

int chk(int idx, int knd){
	int ret = dfs(idx,knd, 0, 0);
	return ret - tall[idx];
}

int main()
{
#ifdef m_
    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);
#endif
	scanf("%d%d%d", &n, &m, &k);
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= k; j++){
			scanf("%d", &need[i][j]);
		}
	}
	for(int i = 1; i < n; i++){
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		add_edg(u, v, w);
		add_edg(v, u, w);
	}
	for(int i = 1; i <= k; i++){
		for(int j = 1; j <=n; j++){
			A[j][i] = chk(j, i);
//			printf("A[%d][%d] = %d\n", j, i, A[j][i]);
		}
	}
	int len =  (1 << k) - 1;
	for(int i = 1; i <= len; i++){
		int mm = INF;
		for(int j = 1; j <= n; j++){
			int temp = 0;
			for(int u = 0; u < k; u++){
				if(i & (1 << u)){
					temp = max(temp, A[j][u + 1]);
				}
			}
			mm = min(mm, temp);
		}
		dp[i][1] = mm;
	}
	
	for(int i = 2; i <= m; i++){
		for(int j = 1; j <= len; j++){
			dp[j][i] = INF;
			for(int u = j; u ; u = (u - 1) & j){
				dp[j][i] = min(dp[j][i], max(dp[j ^ u][i - 1], dp[u][1]));
			}
		}
	}
//	for(int i = 1; i <= m; i++){
//		printf("%d\n", dp[len][i]);
//	}
	cout<<dp[len][m]<<endl;
#ifdef m_
    fclose(stdin);
//    fclose(stdout);
#endif
    return 0;
}