超頂点を用いる． \(a,b\) が空港同士とする． \(a,b\) を直接結ぶのではなく，超頂点 \(\tilde{v}\) を経由して， \(a\) - \(\tilde{v}\) - \(b\) とする． これにより， 頂点 \(a,b\) が空港であるという情報を 辺に移すことができた ので， 連結性の判定が楽になった． 港も同様．
実装は，空港，港を使うか否かで 4通り全て試せばよい． あとはクラスカル法．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n, m, k, q;
cin >> n >> m;
vll x(n), y(n);
rep(i,n) cin >> x[i];
rep(i,n) cin >> y[i];
rep(i,m){
ll a,b,z; cin >> a >> b >> z;
--a, --b;
ed.push_back({z, a, b});
}
// n : airport
// n+1: harbor
rep(i,n){
ed.push_back({x[i], i, n});
ed.push_back({y[i], i, n+1});
}
sort(all(ed));
ll ans = INFL;
rep(s,4){
// 0 : not use
bool fa = s & 1;
bool fh = s >> 1;
ll nn = n;
nn += fa; nn += fh;
UnionFind<ll> uf(n+2);
ll t = 0, nm = 0;
for(auto [co, a, b] : ed){
if(!uf.same(a,b)){
uf.merge(a,b);
t += co;
nm++;
}
}
if(nm == nn - 1) chmin(ans, t);
}
cout << ans << endl;
return 0;
}
