#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define _rep(i, x, y) for(int i = (int)x; i < (int)y; ++i)
#define _dep(i,x,y) for(int i = (int)x; i > (int)y; i--)
#define PII pair<int,int>
#define eb emplace_back
#define pb push_back
#define fi first
#define se second
#define PQ priority_queue
#define lb lower_bound
#define ub upper_bound
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VII;
typedef vector<ll> VL;
typedef vector<vector<ll>> VLL;
constexpr int mod = 1e9 + 7;
constexpr int KINF = 0x3f3f3f3f;
constexpr double eps = 1e-7;
constexpr ll inf = 1e16;
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    VII need(n, VI(k));
    _rep(i, 0, n)
        _rep(j, 0, k) cin >> need[i][j];// 第i号酒店需要食材的情况
    vector<vector<PII>> g(n);
    _rep(i, 1, n){
        int u, v, w;
        cin >> u >> v >> w;
        g[--u].eb(--v, w);
        g[v].eb(u, w);
    }
    VII d(n, VI(k, KINF));
    auto dfs = [&](auto&& dfs, int u, int fa, int id) -> PII{
        PII res = {0, -1};
        if(need[u][id]) res.se = 0;
        for(auto& [v, w] : g[u]){
            if(v == fa) continue;
            PII tmp = dfs(dfs, v, u, id);
            if(tmp.se != -1){
                res.fi += tmp.fi + w * 2;// 每条边都来回走两遍
                res.se = max(res.se, tmp.se + w);// 最长链
            }
        }
        return res;
    };
    _rep(i, 0, n)
        _rep(j, 0, k){
            PII res = dfs(dfs, i, -1, j);
            if(res.se != -1) d[i][j] = res.fi - res.se;// 由该点出发的货车在最长的路上走一遍,其他的路上走两遍最优
        }
    auto check = [&](int time){
        VI dp(1 << k, m + 1);
        dp[0] = 0;
        VI state(n, 0);
        _rep(i, 0, n)
            _rep(j, 0, k){
                if(d[i][j] <= time) state[i] |= (1 << j);
            }
        _rep(bit, 0, (1 << k)){
            if(dp[bit] == m + 1) continue;
            _rep(i, 0, n){
                dp[bit | state[i]] = min(dp[bit | state[i]], dp[bit] + 1);
            }
        }
        return dp[(1 << k) - 1] <= m;
    };
    int l = 0, r = 2e8;
    while(l < r){
        int mid = (l + r) >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
    return 0;
}