[abhishekjha]

This is a pretty good explanation. Putting nodes in a priority queue at each stage is the trick here. I wish I had this explained in such a simple manner earlier.