Задача о минимальном остовном дереве решается двумя алгоритмами - Крускала и Прима. Оба алгоритма находят минимальные деревья, которые минимальны не только по сумме весов всех ребер, но и по весу максимального ребра. (минимальное остовное дерево является минимальным и в таком смысле) но не всякое дерево, обладающего такими свойствами, является минимальным остовным деревом, отсюда можно предположить, что предложенную задачу возможно решать за время O(n + m) (O(V + E) ) Прима и Крускала можно реализовать за N Log N, где N = V+E (можно и поточнее оценки строить, ну да неважно, главное присутствие логарифма. возможно в данной задаче можно обойтись без него.

Идея примерно в следующем:
Находите медианное ребро, то есть такое, которое стояло бы в середине списка отсортированных по весу ребер. Затем строите граф, который состоит только из ребер, которые не больше по весу, чем это медианное. С помощью dfs узнаете является граф связным или нет. Дальше в зависимости от этого, либо добавляете навсегда в граф ребра, меньшие медианы, и сдвигаете левую границу на минимальное используемое ребро, либо просто сдвигаете правую границу, ничего не добавляю в граф. Получается что-то типа бинпоиска.
Утверждается, что при аккуратной реализации того, что я описал получится примерно то, что нужно и все за линейное время(O(n+m)).

UPD: O(n + m)

При реализации нужно очень аккуратно красить компоненты связности и отменять раскраску примерно таким же методом запоминания, который *Alias* написал выше про DSU.