\(N+2\) 頂点のグラフであって、最初どの \(2\) 頂点の間にも辺が貼られていないようなものを考えます。これに対して、

• 島 \(i\) に空港を建設 \(\leftrightarrow\) 頂点 \(i\) と頂点 \(N+1\) の間に辺を張る
• 島 \(i\) に港を建設 \(\leftrightarrow\) 頂点 \(i\) と頂点 \(N+2\) の間に辺を張る
• 島 \(A_i\) と島 \(B_i\) の間に道路を建設 \(\leftrightarrow\) 頂点 \(A_i\) と頂点 \(B_i\) の間に辺を張る

と対応させると、いくつかの交通手段を建設した後で島 \(U\) から 島 \(V\) まで移動できる事は対応する辺を追加した後で 頂点 \(U\) と頂点 \(V\) が同じ連結成分に属する事と同値である事が分かります。

よって、どの島の間も移動できる事は頂点 \(1,2,\ldots, N\) が同じ連結成分に属することと同値になります。最小コストを達成する建設の仕方に対応する辺の張り方をした時の頂点 \(1,2,\ldots, N\)を含む連結成分を構成する頂点集合は \(N+1, N+2\) をそれぞれ含むか否かで \(2^2=4\) 通り考えられます。よって、それぞれの場合に対して、連結にするための最小コストを求め、さらにそれらの最小値を取れば良いです。

最終的な連結成分の頂点集合を固定して考えます。 この時、この問題は最小全域木を求める問題として考える事ができます。 \(N+2\) 頂点の重み付き無向グラフ \(G\) であって、建設できる交通手段に対応する辺とそのコストを重みとするようなものを考えます。 最終的な連結成分が \(N+2\) 頂点全体であった場合、 求めたいコストの最小値は \(G\) の最小全域木の辺の重みの総和になります。

連結成分の頂点集合が全体でない時は、最小コストを求める上で 両端がその頂点集合に属しているような辺のみを考えればよく、 その頂点集合によって誘導される \(G\) の部分グラフ（その固定した頂点集合に属する頂点と両端がその頂点集合に属しているような辺のみを考えたグラフ）\(G'\) における最小全域木の辺の重みの総和がその時の最小コストとなります。 ただし、 \(G'\) が連結でない場合は 最小全域木を構成する事ができないため、コストは \(+\infty\) となります。

よって、これらの最小値を取ることで答を求める事ができました。 なお、頂点 \(N+1\), \(N+2\) は頂点 \(1,2,\ldots, N\)の全てと繋がっているため、最終的な答が \(+\infty\) となることはありません。

\(G\) は \(N+2\) 頂点 \(2N+M\) 辺のグラフであり、最小全域木はクラスカル法などを使うことで \(O((N+M)\log(N+M))\)で求める事ができます。 よって、十分高速にこの問題を解く事ができました。

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;

}