BFS Shortest Path with Neighbor Cost

import time
start = time.time()

graph = {'M': set(['U', 'H']),
    'U': set(['M', 'D', 'A']),
    'H': set(['M', 'F']),
    'A': set(['U', 'I']),
    'D': set(['A', 'F']),
    'F': set(['H', 'R']),
    'I': set(['L']),
    'L': set(['D', 'C']),
    'R': set(['L', 'N']),
    'C': set(['I', 'N']),
    'N': set(['L'])
}

costs = {
    'M': {
        'U': 5,
        'H': 8
    },
    'U': {
        'M': 10,
        'D': 6,
        'A': 9
    },
    'H': {
        'M': 12,
        'F': 3
    },
    'A': {
        'U': 2,
        'I': 15
    },
    'D': {
        'A': 11,
        'F': 13
    },
    'F': {
        'H': 4,
        'R': 1
    },
    'I': {
        'L': 7
    },
    'L': {
        'D': 16,
        'C': 18
    },
    'R': {
        'L': 17,
        'N': 20
    },
    'C': {
        'I': 21,
        'N': 19
    },
    'N': {
        'L': 14
    }
}

def bfs_paths(graph, costs, start, goal):
    route, list_cost = [(start, [start])], []
    while route:
        (vertex, path) = route.pop(0)
        for next in graph[vertex] - set(path):
            # tetangganya juga diitung iyh
            list_cost.append(costs[vertex][next])
            if next == goal:
                yield path + [next], list_cost
            else:
                route.append((next, path + [next]))

def bfs_shortest_path(graph, costs, start, goal):
    try:
        return next(bfs_paths(graph, costs, start, goal))
    except StopIteration:
        return None

bfs_sp, list_cost = bfs_shortest_path(graph, costs, 'M', 'N')
print("Best route: ", bfs_sp)
print("Total cost: ", sum(list_cost))
print("Spent time:", time.time() - start, "seconds.")

'''
Best route:  ['M', 'H', 'F', 'R', 'N']
Total cost:  91
Spent time: 3.24249267578125e-05 seconds.
'''