def astar(graph, h, start, goal):
    open_list = [start]
    closed = []
    g = {start: 0}
    parent = {start: None}

    while open_list:
        current = min(open_list, key=lambda x: g[x] + h[x])

        print(f"\nCurrent Node: {current}")
        print("Open List:", open_list)

        if current == goal:
            path = []
            while current is not None:
                path.append(current)
                current = parent[current]

            print("\nGoal Reached!")
            print("Path:", path[::-1])
            return

        open_list.remove(current)
        closed.append(current)

        for neighbor, cost in graph[current]:
            print(f"  Checking neighbor: {neighbor}")

            if neighbor in closed:
                print(f"    {neighbor} already in closed list")
                continue

            new_g = g[current] + cost
            f = new_g + h[neighbor]

            print(
                f"    g({neighbor})={new_g}, "
                f"h({neighbor})={h[neighbor]}, "
                f"f({neighbor})={f}"
            )

            if neighbor not in open_list:
                open_list.append(neighbor)
            elif new_g >= g.get(neighbor, float('inf')):
                continue

            g[neighbor] = new_g
            parent[neighbor] = current

graph = {
    'A': [('B', 1), ('C', 3)],
    'B': [('D', 3), ('E', 6)],
    'C': [('E', 2)],
    'D': [('G', 4)],
    'E': [('G', 1)],
    'G': []
}

h = {
    'A': 7,
    'B': 6,
    'C': 4,
    'D': 4,
    'E': 1,
    'G': 0
}

astar(graph, h, 'A', 'G')