# Define the graph
graph = {
    'A': {'D': 3, 'B': 5, 'C': 8},
    'D': {'F': 7},
    'B': {'E': 2},
    'C': {'F': 3, 'E': 3},
    'F': {'G': 1},
    'E': {'H': 1},
    'H': {'G': 2}
}

# Define heuristic values
heuristic = {
    'A': 40,
    'D': 35,
    'B': 32,
    'C': 25,
    'E': 19,
    'F': 17,
    'H': 10,
    'G': 0  # Goal
}

def a_star_algorithm(start, goal):
    # Open list as a simple list of tuples (total_cost, node)
    open_list = [(0, start)]
    
    # Dictionary to store the cost of reaching each node
    g_costs = {start: 0}
    
    # Dictionary to reconstruct the path
    came_from = {}
    
    while open_list:
        # Sort the open list by the first element (f_cost) and pop the smallest
        open_list.sort()
        _, current = open_list.pop(0)
        
        if current == goal:
            # Reconstruct the path
            path = []
            while current in came_from:
                path.append(current)
                current = came_from[current]
            path.append(start)
            path.reverse()
            return path, g_costs[goal]
        
        # Process neighbors
        for neighbor, weight in graph.get(current, {}).items():
            tentative_g_cost = g_costs[current] + weight
            if neighbor not in g_costs or tentative_g_cost < g_costs[neighbor]:
                g_costs[neighbor] = tentative_g_cost
                f_cost = tentative_g_cost + heuristic[neighbor]
                open_list.append((f_cost, neighbor))
                came_from[neighbor] = current
    
    return None, float('inf')  # If no path is found

# Run the A* algorithm
start_node = 'A'
goal_node = 'G'
path, cost = a_star_algorithm(start_node, goal_node)

print("Path:", path)
print("Cost:", cost)