Simple application of Floyd-Warshall algorithm for directed graphs O(n^3).
After running the algorithm we need to search main diagonal for minimum amount, which is additional O(n).