Reconstruct graph of N edges from a matrix of shortest pair distances (N*N) (i.e. result from Floyd-Warshall algorithm)
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.