すべての道が沈んでしまった状態から、時間を逆回しすることを考えます。 すると、次のような問題を解くことになります。

はじめ、どの島どうしも繋がれていない。 \(M\) 本の道が追加されていくため、全ての島が連結になった時刻を求めよ。

これは、Union Find などを用いることで \(O(M\alpha(N))\) 時間で解くことができます。

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

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
#include <atcoder/dsu>

int main() {
    unsigned N, M;
    std::cin >> N >> M;

    std::vector<std::tuple<unsigned, unsigned, unsigned>> roads(M);
    for (auto&&[A, B, D] : roads)
        std::cin >> A >> B >> D;

    // 通行止めになる日が遅いほうから道を並べる
    std::ranges::sort(roads, std::greater<>{}, [](const auto &road) { return get<2>(road); });

    // 連結成分を管理
    atcoder::dsu connected_component(N);

    // 時間を遡って
    for (const auto&[A, B, D] : roads) {
        // 道を復活させる
        connected_component.merge(A - 1, B - 1);
        // すべての町が連結になったとき = 連結成分のサイズが N になったときの D が答え
        if (connected_component.size(0) == N) {
            std::cout << D << std::endl;
            return 0;
        }
    }
    return 0;
}