色を \(3\) 種類以上使っているとき、適当な \(2\) 色を同じ色にまとめることを繰り返して \(2\) 種類になるまで色を減らしても違和感コストは増加しません。 また、使っている \(2\) 種類の色の差が \(2\) 以上のとき、差が \(1\) であるような \(2\) 種類の色に置き換えても違和感コストは増加しません。

以上のことから、この問題は次のように言い換えられます。

与えられた木の頂点を空でない \(2\) つの集合 \(S,T\) に分ける。 \(S\) の頂点と \(T\) の頂点を結ぶすべての辺の重みの合計を分け方のスコアとし、スコアを最小化せよ。

木は連結なので、\(1\) 本以上の辺が \(S\) の頂点と \(T\) の頂点を結びます。 逆に、辺を \(1\) 本選ぶと、その辺を取り除いたときに生じる \(2\) つの連結成分をそれぞれ \(S,T\) とすることで、その辺のみを \(S\) の頂点と \(T\) の頂点を結ぶ辺とすることができます。

よって、求めるものは \(W _ i\) の最小値と等しいです。

これは、\(O(N)\) 時間で求めることができます。

実装例は以下のようになります。

#include <iostream>
using namespace std;

int main() {
    int N, M, K;
    cin >> N >> M >> K;
    int ans = 100000;
    for (int i = 0; i < M; ++i) {
        int u, v, W;
        cin >> u >> v >> W;
        ans = min(ans, W);
    }
    cout << ans << endl;
    return 0;
}

N, M, K = map(int, input().split())

print(min(int(input().split()[2]) for i in range(M)))