Charlie is working on a project about reactions in organic chemistry. He collected some data on the energy produced during each reaction and represented them in a weighted graph with nodes-compounds and weights equal to the energy absorbed. If energy is released, the weights are negative. The graph looks like this:
Charlie needs to choose the types of equipment which can withstand the maximal amount of energy released. Hence, he has to calculate the lowest weight shortest path in the graph, guaranteed that its weight will be negative as usually happens in organic chemistry. Using Johnson's algorithm, help Charlie complete the task and output the weight of the shortest path of all.