def find_minimum_cost_brute_force(number_of_cities, available_power_lines):
    minimum_total_cost = 999999999

    # To guarantee finding the optimal grid, we must test every possible combination of power lines.

    for subset_size in range(1, len(available_power_lines) + 1):
        # Note: This code assumes 'itertools.combinations' is available.
        for power_line_subset in itertools.combinations(available_power_lines, subset_size):

            # To be a valid solution, a set of lines must connect all cities into one network.

            parent_map = list(range(number_of_cities))
            number_of_components = number_of_cities

            def find_root(city_index):
                if parent_map[city_index] == city_index:
                    return city_index
                parent_map[city_index] = find_root(parent_map[city_index])
                return parent_map[city_index]

            def union_components(city_one, city_two):
                nonlocal number_of_components
                root_one = find_root(city_one)
                root_two = find_root(city_two)
                if root_one != root_two:
                    parent_map[root_two] = root_one
                    number_of_components -= 1

            for line_city_one, line_city_two, _ in power_line_subset:
                union_components(line_city_one, line_city_two)

            # We only calculate the cost for valid grids that link every city into a single component.

            if number_of_components == 1:
                current_subset_cost = sum(cost for _, _, cost in power_line_subset)

                # The total cost is updated if this valid grid is cheaper than the best one found so far.

                minimum_total_cost = min(minimum_total_cost, current_subset_cost)

    if minimum_total_cost == 999999999:
        return -1
    else:
        return minimum_total_cost

def power_grid_maintenance(number_of_cities, all_potential_lines):
    parent_of_city = list(range(number_of_cities))

    def find_island_representative(city_index):
        if parent_of_city[city_index] == city_index:
            return city_index
        # Path compression makes subsequent lookups for this city and its children much faster.
        parent_of_city[city_index] = find_island_representative(parent_of_city[city_index])
        return parent_of_city[city_index]

    # Sort all potential connections by cost to greedily evaluate the cheapest options first.
    all_potential_lines.sort(key=lambda line_details: line_details[2])

    total_maintenance_cost = 0
    number_of_lines_built = 0

    for city_one, city_two, connection_cost in all_potential_lines:
        root_for_city_one = find_island_representative(city_one)
        root_for_city_two = find_island_representative(city_two)

        # A connection is only useful if it joins two previously disconnected grid sections.
        if root_for_city_one != root_for_city_two:
            total_maintenance_cost += connection_cost
            
            # Merge the two separate islands, effectively building the new power line.
            parent_of_city[root_for_city_two] = root_for_city_one
            
            number_of_lines_built += 1
            if number_of_lines_built == number_of_cities - 1:
                break
    
    return total_maintenance_cost