Find the minimal tank capacity to be able to travel from any city to any other
We first sort all edges according to their costs from small to large. Say the sorted edges are $e_1,e_2,\ldots,e_{n(n-1)}$, and the corresponding costs are $w_1\le w_2\le\cdots\le w_{n(n-1)}$. Then we find the minimal $i$ such that the graph is strongly connected only with the edges $e_1,\ldots,e_i$. Now $w_i$ is the minimal tank capacity we want.

Sorting costs $O(n^2\log n)$ time. To find the minimal $i$, we can use the bisection method. We first test whether the graph is strongly connected with the edges $e_1,\ldots,e_{n(n-1)/2}$. If yes, we then test the connectivity with the edges $e_1,\ldots,e_{\lceil n(n-1)/4\rceil}$, otherwise we test the connectivity with the edges $e_1,\ldots,e_{\lceil3n(n-1)/4\rceil}$, and so on. The running time to find the minimal $i$ is also $O(n^2\log n)$. So the total running time of this algorithm is $O(n^2\log n)$.