I tried all the samples from the discussion and I tried some exception conditions. The program works for all these samples.
Do you have any idea what can be wrong? I can share my C++ code.

Tried disconnected graphs, individual nodes, just a path, and zero edge and node weights. It works for all of the cases :/