import itertools

graph = {
    'A': {'B': 10, 'C': 15, 'D': 20},
    'B': {'A': 10, 'C': 35, 'D': 25},
    'C': {'A': 15, 'B': 35, 'D': 30},
    'D': {'A': 20, 'B': 25, 'C': 30}
}

cities = list(graph.keys())

min_cost = float('inf')
best_path = None

for perm in itertools.permutations(cities[1:]):

    path = ['A'] + list(perm) + ['A']

    cost = 0

    for i in range(len(path) - 1):
        cost += graph[path[i]][path[i + 1]]

    if cost < min_cost:
        min_cost = cost
        best_path = path

print("Best Path:")
print(best_path)

print("Minimum Cost:")
print(min_cost)