from itertools import permutations

def traveling_salesman(cities, distances):
    n = len(cities)
    min_distance = float('inf')
    best_route = None
    for route in permutations(cities):
        current_distance = 0
        for i in range(n):
            current_distance += distances[route[i]][route[(i + 1) % n]]
        if current_distance < min_distance:
            min_distance = current_distance
            best_route = route
    return best_route, min_distance

if __name__ == "__main__":
    cities = ['A', 'B', 'C', 'D']
    distances = {
        'A': {'A': 0, 'B': 10, 'C': 15, 'D': 20},
        'B': {'A': 10, 'B': 0, 'C': 35, 'D': 25},
        'C': {'A': 15, 'B': 35, 'C': 0, 'D': 30},
        'D': {'A': 20, 'B': 25, 'C': 30, 'D': 0}
    }
    best_route, min_distance = traveling_salesman(cities, distances)
    print(f"Best Route: {' -> '.join(best_route)}")
    print(f"Minimum Distance: {min_distance}")