Borouvka 法を使います．

各反復の段階では，各頂点 \(v\) から他の成分への辺で重みが最小のものを探すことになります．

連結成分 \(C_1, \ldots, C_K\) があり，\(v\in C_i\) からの辺を探しますが，

• \(j<i\) であるような \(C_j\) への辺
• \(j>i\) であるような \(C_j\) への辺

に分けてそれぞれ求めることにします．すると，

• 点 \((a,b)\) の追加
• \((x,y)\) が与えられるので \(ax+by\) が最小の \((a,b)\) を求める

という \(2\) つの操作ができればよくなり，これは凸包または CHT に関する基本的なクエリ処理です（\(2\) 方向に分けたことで削除操作が不要になっています）．

Borouvka 法の反復ごとに \(O(N\log N)\) 時間がかかり，全体で \(O(N\log^2N)\) 時間で答えを計算できます．