All pairs shortest paths

Input

A directed graph [math]\displaystyle{ G = (V,A) }[/math]
An arc length [math]\displaystyle{ l(a) \in \mathbb{R} }[/math] for each arc [math]\displaystyle{ a \in A }[/math]

For each pair [math]\displaystyle{ (v,w) \in A }[/math] with [math]\displaystyle{ v,w \in V }[/math]:

The length [math]\displaystyle{ \Delta(v,w) }[/math] of a shortest [math]\displaystyle{ (v,w) }[/math]-path in [math]\displaystyle{ G }[/math] with respect to [math]\displaystyle{ \ell }[/math] among all paths that have at most [math]\displaystyle{ |V| }[/math] arcs.
The last arc (pointing to [math]\displaystyle{ w }[/math]) of one of these paths.

Remark:

Obviously, if no [math]\displaystyle{ (v,w) }[/math]-path meets any negative cycle, a shortest path exists, and at least one shortest path is simple (because such a path may only contain cycles of zero total length, which may be removed). This path has at most [math]\displaystyle{ |V|-1 }[/math] arcs. On the other hand, if there are negative cycles, there is, evidently, at least one simple negative cycle. A simple cycle has at most [math]\displaystyle{ |V| }[/math] arcs. Therefore, the distance from [math]\displaystyle{ v }[/math] to [math]\displaystyle{ w }[/math] in the output is negative. Of course, the case [math]\displaystyle{ v=w }[/math] is included. The nodes [math]\displaystyle{ v\in V }[/math] with negative distance [math]\displaystyle{ v\rightarrow v }[/math] are exactly the nodes on negative simple cycles.
The path (or negative cycle) itself may be easily reconstructed backwards along the incoming arcs (output #2).

Polynomial