from heapq import heappop, heappush

def ucs_gsa(graph, start, goal, trace=False):
    frontier = [(0, start)]
    explored = set()
    explored_order = []
    while frontier:
        cost, path = heappop(frontier)
        state = path[-1]
        if state == goal:
            return cost, path, explored_order
        if state in explored:
            continue
        explored.add(state)
        explored_order.append(state)
        for step_cost, child in graph[state]:
            heappush(frontier, (cost + step_cost, path + child))
        if trace:
            print(f"{path} @ {cost} -> {sorted(frontier)}")
            print(f"explored: {sorted(explored)}\n")

romania = {
    "A": [(140, "S"), (118, "T"), (75, "Z")],
    "Z": [(75, "A"), (71, "O")], "O": [(151, "S"), (71, "Z")],
    "T": [(118, "A"), (111, "L")], "L": [(70, "M"), (111, "T")],
    "M": [(75, "D"), (70, "L")], "D": [(120, "C"), (75, "M")],
    "S": [(140, "A"), (99, "F"), (151, "O"), (80, "R")],
    "R": [(146, "C"), (97, "P"), (80, "S")],
    "C": [(120, "D"), (138, "P"), (146, "R")],
    "F": [(211, "B"), (99, "S")], "P": [(101, "B"), (138, "C"), (97, "R")],
    "B": [],
}
cost, path, order = ucs_gsa(romania, "A", "B", True)
print("solution:", (cost, path))
print("explored order:", " -> ".join(order))