Let G = (V,E) be a directed graph with positive costs, i.e. c_e 0 for every e E. The following is true for every real number > 0. Consider the instance where the input graph is still G but the costs are now (for every e E). Then for some distinct s,t V, the shortest s-t path in the two instances are different.