If a Bellman-Ford algorithm is run for n-1 iterations on a graph that does have shortest paths from the source nodes to all the other nodes, then by the end of the n-1’th iteration, all the shortest paths can be found. Since any edges of the given graph can have a weight from -1000 to 1000 and the graph has 500 nodes, it’s easy to see what could be the highest or lowest cost of a valid shortest path from source to any other node. Bellman-Ford also signals the existence of a cycle if the n’th iteration is performed. Thus, understanding and applying the principles of Bellman-Ford algorithm is enough to solve this problem. Since the original graph is not given and the graph may have self self, some tricky cases may arise.