Consider a graph with \(N+2\) vertices that initially has no edges. Let us correspond

• building an airport on island \(i\) \(\leftrightarrow\) add an edge between vertices \(i\) and \(N+1\);
• building a harbor on island \(i\) \(\leftrightarrow\) add an edge between vertices \(i\) and \(N+2\);
• building a road between island \(A_i\) and \(B_i\) \(\leftrightarrow\) add an edge between vertices \(A_i\) and \(B_i\),

then, after building some facilities, one can travel from islands \(U\) to \(V\) if and only if vertices \(U\) and \(V\) belong to the same connected component after adding corresponding edges.

Therefore, one can travel between any two islands if and only if \(1,2,\ldots, N\) belongs to the same connected component. There are four possible vertex sets for a set of the connected component containing vertices \(1,2,\ldots, N\) when we add the edges that correspond to the way of construction that achieves the minimum costs. Thus, for each of the four cases, we can find the minimum cost to make them connected and find their minimum value.

Let us fix a vertex set of the vertex set of the final connected component. Then, this problem can be considered as a problem of finding a minimum spanning tree. Consider a weighted undirected graph \(G\) with \(N+2\) vertices and edges that correspond to the constructable facilities weighted with corresponding cost. When the final connected component is the entire \((N+2)\) vertices, the minimum cost is the sum of the weights of the edges of a minimum spanning tree of \(G\).

When the vertex set of the connected component is not the entire vertices, it is sufficient to consider the edges that both ends belong to the vertex set when finding the minimum cost; the minimum cost for this case is the sum of edges of a minimum spanning tree of the subgraph \(G'\) induced in \(G\) by the vertex set. Here, however, if \(G'\) is not connected, we cannot construct a minimum spanning tree, so the cost is \(+\infty\).

Hence, we could find the answer by taking the minimum of these values. Note that vertices \(N+1\) and \(N+2\) are both connected to all of the vertices \(1,2,\ldots, N\), so the final answer cannot be \(+\infty\).

Since \(G\) is a graph with \((N+2)\) vertices and \((2N+M)\) edges, the minimum spanning tree can be found with an algorithm like Kruskal’s algorithm in a total of \(O((N+M)\log(N+M))\) time. Therefore, the problem has been solved fast enough.

Sample code in C++:

#include <bits/stdc++.h>
#include <atcoder/dsu>

using namespace std;
using namespace atcoder;

#define INF (long long)3e+18

int n,m;
vector<tuple<long long,int,int> >e;

long long solve(void){
	long long ret=0;
	sort(e.begin(),e.end());
	int sz=e.size();
	
	dsu d(n+3);
	for(int i=0;i<sz;i++){
		if(!d.same(get<1>(e[i]),get<2>(e[i]))){
			d.merge(get<1>(e[i]),get<2>(e[i]));
	 		ret+=get<0>(e[i]);
        	}
    }
   
	if(d.size(1)<n)return INF;
	return ret;
}



int main(void) {

    cin>>n>>m;

    vector<int> a(m),b(m);
    vector<long long> x(n),y(n),z(m);

	for(int i=0;i<n;i++)cin>>x[i];
	for(int i=0;i<n;i++)cin>>y[i];
	for(int i=0;i<m;i++){
		cin>>a[i]>>b[i]>>z[i];
	}

	long long ans=INF;
	for(int k=0;k<4;k++){
		e.clear();
		if(k&1)for(int i=0;i<n;i++)e.push_back({x[i],i+1,n+1});
		if(k&2)for(int i=0;i<n;i++)e.push_back({y[i],i+1,n+2});
		for(int i=0;i<m;i++)e.push_back({z[i],a[i],b[i]});
		ans=min(ans,solve());
	}
	cout<<ans<<endl;

}