Here are my whiteboard notes for solving this problem:
And here is my c++ source code for the solution:
https://gist.github.com/adamkorg/fb698c0785845576ff0b42a091547691
Initially I started off with what I thought was a simple inefficient way of finding the next smallest node but the implementation was actually a little complicated. The multimap version is more time efficient and possibly has less complicated edge cases. I think an even more efficient way to keep track of the smallest node would be to use a priority queue.