from collections import deque

def bfs(graph, start, goal):
    visited = set()
    queue = deque([(start, [start], 0)])
    
    while queue:
        current, path, cost = queue.popleft()
        
        if current == goal:
            return path, cost
        
        visited.add(current)
        
        for neighbor, edge_cost in graph.get(current, []):
            if neighbor not in visited:
                queue.append((neighbor, path + [neighbor], cost + edge_cost))
    
    return None, None

# Sample graph (replace or extend as needed)
graph = {
    "kavali": [("ongole", 40), ("nellore", 50)],
    "ongole": [("guntur", 70)],
    "nellore": [("tirupati", 130)],
    "guntur": [],
    "tirupati": []
}

# Input
start_city = "kavali"
goal_city = "tirupati"

# Run BFS
path, total_cost = bfs(graph, start_city, goal_city)

# Output
if path:
    print("Path:", " -> ".join(path))
    print("Total cost:", total_cost)
else:
    print("No path found.")