# Q2

n = int(input("Enter number of cities (at least 8): "))
graph = {}
h = {}

for i in range(n):
    city = input("Enter city name: ")
    h[city] = int(input("Enter heuristic: "))
    graph[city] = {}

for i in range(int(input("Enter number of roads: "))):
    a, b, cost = input("Enter city1 city2 distance: ").split()
    graph[a][b] = int(cost)
    graph[b][a] = int(cost)

start = input("Enter source: ")
goal = input("Enter destination: ")

q = [(h[start], 0, start, [start])]
visited = []

while q:
    q.sort()
    hv, g, city, path = q.pop(0)

    if city == goal:
        print("Route:", path)
        print("Total cost:", g)
        print("Nodes explored:", len(visited))
        break

    if city in visited:
        continue
    visited.append(city)

    for nxt, cost in graph[city].items():
        if nxt not in visited:
            q.append((h[nxt], g + cost, nxt, path + [nxt]))
else:
    print("No route found")



