Give G lots of edges and make every edge count for lots updates in the heap.