In Priority queue realization in docs https://docs.python.org/3/library/heapq.html there is no appointments that priority can be equal and the task can have different type. For example, if you store number of graph node in your priority queue, than it is possible to get "TypeError: '<' not supported between instances of 'int' and 'str'", because inside heappop there is comparison between elements, and if the fist elements the same, than it compare tasks, which can be tagged as removed and has '<removed-task>' value as opposed to number of node, which is int.