def find_paths(cities_left, location_distances, total_distance, path):
    """Find possible paths between cities_left, with location_distances."""
    if len(cities_left) == 1:
        return [(total_distance, path)]
    paths = []
    source_cities = [path[-1]] if path else cities_left
    for city in source_cities:
        next_path = path if path else [city]
        next_cities = cities_left - {city}
        for target, distance in location_distances[city]:
            if target not in next_cities:
                continue
            paths.extend(find_paths(next_cities.copy(),
                                    location_distances,
                                    total_distance + distance,
                                    next_path + [target]))
    return paths