All-pairs shortest return paths without reusing edges

Question

All-pairs shortest paths is a standard pathfinding problem. This is a twist on that.

Definitions

We are searching for paths on a directed graph. Graphs are defined by square matrices, for example

0  3  2.5
1  0  1
0 -1  0

Write M(r,c) = value in M at row r, column c is the cost to travel from node r to node c. The graph is in general asymmetric, costs may be negative, and M(i,i)=0 for all i. An edge with cost zero does not exist, i.e. treat zeros as infinities in the input.

Indexing from zero, the above graph can be visualised thus:

Goal

For a given valid, input matrix of any size output the matrix MOUT(r,c)=cost of the shortest path from r to c and back to r

The twist is: you must make a return trip, without visiting any edges on the return trip which you used on the outward trip. That is, M(r,c) and M(c,r) are considered to be the same edge albeit with a cost which depends on the direction of travel.

For example, the shortest path from 0 -> 1 -> 0 may not include both the edges (0,1) and (1,0).

Nor may you re-use an edge in the outward trip.

Each return trip is considered independently of the others. If you use (0,1) in the path from 0 -> 1 -> 0 then you may use either (0,1) or (1,0) in the path from 0 -> 2 -> 0.

Input/Output Format

Input is on stdin and output on stdout.

The input and output is a matrix with columns separated by a number of spaces, and rows separated by a single \n.

Input entries are floating point numbers conforming to /^-?[0-9]+(\.[0-9]*)?$/. Output entries are numbers of the same kind or Inf, Infinity, or NaN or some equivalent symbol in the event that no return route exists between those nodes. A zero in the input matrix represents an infinite cost (non-existant edge) but zeroes in the output represent a cost-free journey.

Your program behaviour is undefined in the event that the input is not a finite real-valued square matrix.

Requirements

Test against the following input matrices and post the results with your code.

A:

 0   6  -5  -2   9
-3   0   0  -4   5
 7   2   0  -8   1
-6   3   4  0  -9
 8  -3  -1  2    0

B:

 0  -0.3  2.4  -1
 1   0    0.9   9.3
10   4    0   -2 
 8  -6  -7  0

C:

0  1   0   2
0  0   3   1
4  0   0   2
0  1   0   1

Shortest code wins.