Задачка на графы про города и деревни

Вот у меня есть такая вот задача:
В стране есть k городов и n деревень, причём между городами нет прямых дорог, т.е. Нет такой дороги которая ведет из города в город. В этой стране есть m однонаправленных дорог с заданными длинами. Гарантируется, что соответствующий граф ацикличен. Мне нужно оставить некоторое подмножество рёбер, так чтобы из любого города можно было добраться в любую деревню (новые дороги строить нельзя). Мне нужно найти минимальный суммарный вес выбранных дорог за O(k + n + m + n log k).