Reconstruct graph of N edges from a matrix of shortest pair distances (N*N) (i.e. result from Floyd-Warshall algorithm) I want to reconstruct a graph when given the results of a Floyd-Warshall shortest pair distances matrix, similar to the problem being solved in this question:

Is it possible to reconstruct graph if we have given matrix of shortest pairs

The only difference being that, whilst the problem from the linked-to question seeks to find a graph of $N-1$ edges, I want to produce a graph containing $N$ edges.

I've already found a more efficient way of solving the problem from the question linked above. Instead of using the solution offered there, I have found that building a minimal spanning tree also yields the correct result, namely a graph of $N-1$ edges that, when given as input to the Floyd-Warshall algorithm, produces exactly the matrix of minimum distance pairs with which we started.

Now we have one edge left to add. This is the part I am unable to figure out. It boils down to this:

I have a graph of $N-1$ edges, which is represented by a matrix of shortest pair distances. Out of a list of candidate edges, how can I efficiently (i.e. without brute forcing) find which edge to add that does not change even a single value in the matrix, preserving all minimum distances?

Thanks!
Pick any pair of vertices $u,v$ where it is possible to reach $v$ from $u$.  Add an edge $u \to v$ with a length that is really large.