Floyd-Warshall all-pairs shortest path

Here's an algorithm that can tolerate negative edges (but not negative cycles, even with only 2 vertices) and returns a table of the shortest distance between all pairs of vertices.

The idea is to first find all the minimal distances for pairs without using any intermediate vertices (this is easy to calculate, since it will be $\infty$ if no edge exists between the pair, the edge weight otherwise). We then relax the restriction, step-by-step: first allow paths that use node 0 as an intermediate, and see whether the minimum distances can be adjusted downwards, then paths that are allowed to use nodes 0 and 1, and so on until all paths are considered. We denote the minimum distance from $v_i$ to $v_j$ that considers intermediate nodes from the set $\{0, \ldots, k\}$ as $D[i, j, k]$ (special case, $D[i,j,-1]$ doesn't allow any intermediate nodes).

Now we have a way of building up results. If we already know $D[i,j,m]$, for $m \in \{0, \ldots, k-1\}$, and every pair $(i,j)$, then the shortest path from $i$ to $j$ either passes through $k$ or it doesn't. In the first case, the portion of this minimal path from $i$ to $k$ is itself minimal and doesn't use $k$ (convince your self of this), as is the portion from $k$ to $j$, so $D[i, j, k]$ = $D[i,k,k-1]$ + $D[k,j,k-1]$. In the second case, $D[i, j, k]$ equals $D[i,j,k-1]$.

Since we can easily calculate $D[i,j,-1]$ for all pairs $(i,j)$, we can build up to $D[i,j,n]$ (where $n=\vert V\vert$) as follows (the third parameter is suppressed, but corresponds to the outer loop parameter $k$ in the bottom triply-nested loop):

      FLOYD-WARSHALL( V, E )
         for  i := 0  to  n-1  do
            for  j := 0  to  n-1  do
               if  i == j  then
                  D[i,j] := 0;
               else if  (i,j) is in E  then
                  D[i,j] := w(i,j); /* <-- weight function w */
               else
                  D[i,j] := oo;
               end if
            end for
         end for
         for  k := 0  to  n-1  do
            for  i := 0  to  n-1  do
               for  j := 0  to  n-1  do
                  if  D[i,k] + D[k,j] < D[i,j]  then
                     D[i,j] = D[i,k] + D[k,j];
                  end if
               end for
            end for
         end for
      END

Here's something to worry about. How do you know that $D[i,k]$ and $D[k,j]$ correspond to $D[i,k,k-1]$, $D[k,j,k-1]$, and haven't been updated with minimum distances that pass through $k$?

An easy calculation shows that Floyd-Warshall has $O(n^3)$ complexity, which is consistent with using Dijkstra $n$ times (and much simpler). How would you recover a shortest path, given this table of distances?