Auto comment: topic has been updated by Alexrider726 (previous revision, new revision, compare).

Change the signs of all capacities. This is not a necessary step, but it makes what I am about to explain more straightforward.

Floyd-Warshall gives you for each pair of 2 vertices the best distance between them. In this problem, distance is defined as the maximal weight of an edge that we passed through. Keeping this in mind, we can just run the normal Floyd-Warshall to find the minimal distance, but instead of the distance being $$$d1+d2$$$, it will be $$$max(d1,d2)$$$.

Time complexity is $$$O(N^3)$$$. If instead of Floyd-Warshall we use Dijkstra, the time complexity becomes $$$O(N M log N)$$$, where $$$M$$$ is the number of edges.

However, this problem can also be solved in $$$O(N^2 + M \alpha (N))$$$.

Assume that weights are still inverted.

We will observe that there always exists an optimal path that goes only through the edges of MST (Minimum spanning tree). Therefore we will find the spanning tree of the graph. Now the optimal path between 2 vertices will be their unique path on the MST. We can find the lengths of those paths by running DFS from each vertex.