struct Dsu {
    vector<int> f;
    Dsu(int n) {
        f.assign(n + 1, 0);
        iota(f.begin(), f.end(), 0);
    }

    int fa(int u) {
        return u == f[u] ? u : f[u] = fa(f[u]);
    }

    void merge(int u, int v) {
        f[fa(u)] = fa(v);
    }

    int same(int u, int v) {
        return fa(u) == fa(v);
    }
};

void solve() {
    int n, m, k;
    cin >> n >> m >> k;

    #define a3 array<ll, 3>
    vector<a3> e(m);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        e[i] = {w, u, v};
    }

    vector a(k, vector<int>(n + 1));
    vector<int> c(k), mnid(k, 1);

    for (int i = 0; i < k; i++) {
        cin >> c[i];
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
            if (a[i][j] < a[i][mnid[i]]) {
                mnid[i] = j;
            }
        }
    }
    ll ans = 0;
    sort(e.begin(), e.end());
    Dsu dsu(n);
    vector<a3> ne;
    for (auto [w, u, v] : e) {
        if (dsu.same(u, v)) continue;
        ne.push_back({w, u, v});
        dsu.merge(u, v);
        ans += w;
    }
    vector ke(k, vector<a3>());
    for (int i = 0; i < k; i++) {
        for (int u = 1; u <= n; u++) {
            ke[i].push_back({a[i][u], mnid[i], u});
        }
        sort(ke[i].begin(), ke[i].end());
    }

    for (int x = 0; x < 1 << k; x++) {
        ll res = 0;
        vector<reference_wrapper<vector<a3>>> vec; vec.push_back(ne);
        for (int i = 0; i < k; i++) {
            if (x >> i & 1) {
                res += c[i] + a[i][mnid[i]];
                vec.push_back(ke[i]);
            }
        }
        Dsu dsu(n);

        priority_queue<a3, vector<a3>, greater<a3> > q;
        for (int i = 0; i < vec.size(); i++) {
            q.push((a3){vec[i].get()[0][0], i, 0});
        }
        int cnt = 0;
        while (q.size()) {
            auto [_, ik, i] = q.top(); q.pop();
            auto [w, u, v] = vec[ik].get()[i];
            if (i + 1 < vec[ik].get().size()) {
                q.push((a3){vec[ik].get()[i + 1][0], ik, i + 1});
            }
            if (dsu.same(u, v)) continue;
            dsu.merge(u, v);
            res += w;
            if (++cnt == n - 1) break;
        }
        ans = min(ans, res);
    }
    cout << ans << '\n';
}