import heapq


def _pop_unscanned_candidate(pqueue, scanned):
    """
    Pop out the first unscanned candidate in the pqueue. Return a
    tuple of Nones if no more unscanned candidates found.
    """
    if not pqueue:
        return None, None, None
    while True:
        cost_sofar, candidate, prev_candidate = heapq.heappop(pqueue)
        if not pqueue or candidate.id not in scanned:
            break
    if candidate.id in scanned:
        assert not pqueue
        return None, None, None
    return cost_sofar, candidate, prev_candidate