72pts求条！！

#include <bits/stdc++.h>
using namespace std;
struct E{
    int f,t,w;
};
const int M=1e6+10,N=1e4+10,K = 11;
E o[M],b[N],g[K][N],t[M],c[M];
int p[N],n,m,k;
int cst[K];
int tn;
int bc;
long long mn;
vector<int> s;
int fd(int x){
    if(p[x] != x){
        p[x] = fd(p[x]);
    }
    return p[x];
}
bool cmp(E a, E b){
    return a.w < b.w;
}
void dfs(int i){
    if(i == k + 1){
        int cc = bc;
        for(int j = 1; j <= bc; j++){
            c[j] = b[j];
        }
        long long sum = 0;
        for(int x : s){
            sum += cst[x];
            int a=1,b=1,d=1;
            while(a <= cc && b <= n){
                if(c[a].w < g[x][b].w){
                    t[d++] = c[a++];
                }
                else t[d++] = g[x][b++];
            }
            while(a <= cc){
                t[d++] = c[a++];
            }
            while(b <= n){
                t[d++] = g[x][b++];
            }
            cc = d - 1;
            for(int j = 1; j <= cc; j++){
                c[j] = t[j];
            }
        }
        tn = n + s.size();
        for(int j = 1; j <= tn; j++){
            p[j] = j;
        }
        for(int j = 1; j <= cc; j++){
            int x = fd(c[j].f);
            int y = fd(c[j].t);
            if(x != y){
                p[x] = y;
                sum += c[j].w;
            }
        }
        mn=min(mn,sum);
        return;
    }
    dfs(i + 1);
    if(i <= k){
        s.push_back(i);
        dfs(i + 1);
        s.pop_back();
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> k;
    for(int i = 1; i <= m; i++){
        cin>>o[i].f>>o[i].t>>o[i].w;
    }
    for(int i = 1; i <= n; i++){
        //初始化
        p[i]=i;
    }
    sort(o+1,o+m+1,cmp);
    bc=0;
    mn=0;
    for(int i = 1; i <= m; i++){
        int x = fd(o[i].f);
        int y = fd(o[i].t);
        if(x != y){
            p[x] = y;
            b[++bc] = o[i];
            mn += o[i].w;
        }
    }
    for(int i = 1; i <= k; i++){
        cin >> cst[i];
        for(int j = 1; j <= n; j++){
            g[i][j].f = n + i;
            g[i][j].t = j;
            cin >> g[i][j].w;
        }
        sort(g[i] + 1, g[i] + n + 1,cmp);
    }
    dfs(1);
    cout << mn;
    return 0;
}