Hmm.  It's true that Python 3's comparison rules make PriorityQueue a bit less useful in its current form.

One possible workaround could be to introduce an optional "key" argument to the constructor that provides a callable used to map objects added to the queue to their priorities.  The default key would map each object to itself, as before, but for a use-case like this one the key could just be lambda x: x[0].