O(2^knk) 还能卡吗

#include <bits/stdc++.h>
using namespace std;
#define il inline
#define pb emplace_back
typedef long long ll;
const int N = 3e6 + 10;
struct node
{
	int u, v, w, id;
	friend bool operator < (const node &n1, const node &n2)
	{
		return n1.w < n2.w;
	}
}e[N], b[N];
int head[N], nxt[N], siz, f[N], c[11], a[11][N], n, m, k, tot;
unordered_map<int, int> mp;
il void add(int x, node y)
{
	b[++siz] = y;
	nxt[siz] = head[x];
	head[x] = siz;
}
il int find(int x)
{
	return f[x] == x ? x : f[x] = find(f[x]);
}
set<int> ss;
il ll kruskal(int x)
{
	int nn = n + k;
	ll mst = 0;
	for(int i = 0;i < k;++i)
		if((x >> i & 1)) mst += c[i];
	for(int i = 1;i <= nn;++i) f[i] = i;
	for(auto i : ss)
	{
		for(int j = head[i];j;j = nxt[j])
		{
			if(b[j].id != -1 && !((x >> b[j].id) & 1)) continue;
			if(find(b[j].u) == find(b[j].v)) continue;
			f[find(b[j].u)] = find(b[j].v);
			mst += b[j].w;
		}
	}
	return mst;
}
il int read()
{
	char ch = getchar();
	while(ch < 48 || ch > 57) ch = getchar();
	int x = 0;
	while(48 <= ch && ch <= 57)
	{
		x = (x << 1) + (x << 3) + ch - 48;
		ch = getchar();
	}
	return x;
}
set<int> s;
int main()
{
	n = read(), m = read(), k = read();
	for(int i = 1;i <= m;++i)
	{
		e[i].u = read(), e[i].v = read(), e[i].w = read(), e[i].id = -1;
		s.insert(e[i].w);
	}
	int tmp = 0;
	for(int i = 0;i < k;++i)
	{
		c[i] = read();
		tmp = max(tmp, c[i]);
		for(int j = 1;j <= n;++j)
		{
			a[i][j] = read();
			s.insert(a[i][j]);
		}
	}
	for(auto i : s) mp[i] = ++tot;
	for(int i = 1;i <= n;++i) f[i] = i;
	sort(e + 1, e + 1 + m);
	for(int i = 1;i <= m;++i)
	{
		if(find(e[i].u) == find(e[i].v)) continue;
		add(mp[e[i].w], e[i]);
		ss.insert(mp[e[i].w]);
		f[find(e[i].u)] = find(e[i].v);
	}
	for(int i = 0;i < k;++i)
		for(int j = 1;j <= n;++j)
			add(mp[a[i][j]], (node){n + i + 1, j, a[i][j], i}), ss.insert(mp[a[i][j]]);
	if(!tmp)
	{
		cout << kruskal((1 << k) - 1);
		return 0;
	}
	ll ans = 1e18;
	for(int i = 0;i < (1 << k);++i) ans = min(ans, kruskal(i));
	cout << ans;
	return 0;
}