Traveling salesman problem - negative distances allowed
Hint: Every TSP tour has the same number of edges. Use this to modify the weights in the graph in a way which affects all TSP tours in the same way.