import heapq


def _pop_unscanned_edge(pqueue, scanned_nodes):
    """
    Pop out from the pqueue the first edge whose end node is not
    scanned. Return a tuple of Nones if no more unscanned edges found.
    """
    assert pqueue
    while True:
        cost_sofar, edge = heapq.heappop(pqueue)
        if not pqueue or edge.end_node not in scanned_nodes:
            break
    if edge.end_node in scanned_nodes:
        assert not pqueue
        return None, None
    return cost_sofar, edge