Given a graph with n nodes and m edges, every edge has a passing cost that can be negative, find the minimum distance between node 1 and every other node

We will use the Bellman-Ford algorithm to compute the minimum distance between that start node and every other one, by passing through each edge for a maximum of n times and "relaxing the edge", where possible, to obtain the best path. Also, we will improve the algorithm by using only the nodes that helped us relax a path in the past, the other ones being redundant. This will be done by using a queue and the final algorithm will have an O(n*m) complexity but is much faster in practice.