class SearchNode:
    def __init__(self, vertex, cost, path):
        self.cost = cost
        self.path = path
        self.vertex = vertex

class CityGraph:
    def __init__(self):
        self.edges = {}
        self.distances = {}

    def addEdge(self, fromNode, toNode, distance):
        if fromNode not in self.edges.keys():
            self.edges[fromNode] = []
        if toNode not in self.edges.keys():
            self.edges[toNode] = []
        self.edges[fromNode].append(toNode)
        self.edges[toNode].append(fromNode)
        self.distances[(fromNode, toNode)] = distance
        self.distances[(toNode, fromNode)] = distance

    def findBFSbyCost(self, start, end):
        queue = []
        queue.append(SearchNode(start,0,[start]))
        while queue:
            # get the best candidate vertex
            bestNode = None
            bestPrice = 0
            for sN in queue:
                if bestNode == None or bestPrice > sN.cost:
                    bestNode = sN
                    bestPrice = sN.cost
            # priority queue should do this better
            queue.remove(bestNode)
            # we are at the end vertex
            if bestNode.vertex == end:
                return bestNode.cost, bestNode.path
            # expand current vertex into queue
            for newNode in self.edges[bestNode.vertex]:
                if newNode in bestNode.path:
                    continue
                path = bestNode.path + [newNode]
                cost = bestNode.cost + self.distances[(bestNode.vertex, newNode)]
                queue.append(SearchNode(newNode, cost, path))
        # queue is empty and no solution is found - None is the result



graph = CityGraph()
graph.addEdge('A', 'B', 10)
graph.addEdge('A', 'C', 20)
graph.addEdge('B', 'D', 15)
graph.addEdge('C', 'D', 30)
graph.addEdge('B', 'E', 50)
graph.addEdge('D', 'E', 30)
graph.addEdge('E', 'F', 5)
graph.addEdge('F', 'G', 2)

print(graph.edges)
print(graph.distances)
print(graph.findBFSbyCost('A', 'F'))