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")

practice = {
    "S": [(3, "a"), (2, "d"), (10, "G")], "a": [(5, "b")],
    "d": [(1, "b"), (4, "e")], "b": [(2, "c"), (1, "e")],
    "c": [(4, "G")], "e": [(3, "G")], "G": [],
}
cost, path, order = ucs_gsa(practice, "S", "G", True)
print("solution:", (cost, path))
print("explored order:", " -> ".join(order))