差0.01s险过求条

#include<bits/stdc++.h>
using namespace std;

namespace FastIO {
	template <typename T> inline T read() { T x = 0, w = 0; char ch = getchar(); while (ch < '0' || ch > '9') w |= (ch == '-'), ch = getchar(); while ('0' <= ch && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar(); return w ? -x : x; }
	template <typename T> inline void write(T x) { if (!x) return; write<T>(x / 10), putchar(x % 10 ^ '0'); }
	template <typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; else if (x == 0) putchar('0'); write<T>(x); }
	template <typename T> inline void print(T x, char en) { if (x < 0) putchar('-'), x = -x; else if (x == 0) putchar('0'); write<T>(x), putchar(en); }
};
using namespace FastIO;

typedef long long ll;

struct EDGE {
    int u, v; ll w;
    bool used;
    bool operator < (const EDGE &o) const {return w < o.w; }
};

int n, m, k;
ll ans = 1e18;
vector<EDGE> e;
vector<EDGE> o_e;
vector<int> a(15);

struct DSU {
    int fa[10020];
    vector<EDGE> used_e;

    inline void init(const int &n) {
        for(int i = 1; i <= n; ++i) fa[i] = -1;
        used_e.clear();
    }

    inline int find(const int &x) {
        if(fa[x] < 0) return x;
        else return (fa[x] = find(fa[x]));
    }

    void merge(const int &u, const int &v, const ll &w) {
        int x = find(u), y = find(v);
        if(x == y) return ;
        if(fa[x] > fa[y]) swap(x, y);
        
        fa[x] += fa[y];
        fa[y] = x;

        used_e.push_back(EDGE{x, y, w, true});
    }
} dsu;

ll kruskal() {
    ll ans = 0, cnt = 0;
    for(int i = 0; i < e.size(); ++i) {
        if(!e[i].used) continue;
        
        ll u = dsu.find(e[i].u), v = dsu.find(e[i].v);
        if(u == v) continue;
        ans += e[i].w; cnt++;
        dsu.merge(e[i].u, e[i].v, e[i].w);
        if(cnt == n + k - 1) break;
    }

    return ans;
}

int main() {
    n = read<int>(); m = read<int>(); k = read<int>();
    dsu.init(n + k);
    
    int u, v; ll w;
    for(int i = 1; i <= m; ++i) {
        u = read<int>(); v = read<int>(); w = read<ll>();
        e.push_back(EDGE{u, v, w, true});
    }
    
    sort(e.begin(), e.end());
    ans = kruskal();
    e = dsu.used_e;

    ll x;
    for(int i = 1; i <= k; ++i) {
        a[i] = read<int>();
        for(int j = 1; j <= n; ++j) {
            x = read<ll>();
            e.push_back(EDGE{i + n, j, x, false});
        }
    }

    sort(e.begin(), e.end());

    o_e = e;

    ll value = 0;
    for(ll S = 1; S < (1 << k); ++S) {
        dsu.init(n + k); value = 0;
        for(int i = 1; i <= k; ++i)
            if(S & (1 << (i - 1))) {
                value += a[i];
                for(auto &x : e) if(x.u == i + n) x.used = true;
            }

        value += kruskal();
        ans = min(ans, value);

        e = o_e;
    }

    print(ans);
    
    return 0;
}