Given a directed weighted graph. Find a pair of vertices, the shortest distance from one of them to another is maximum among all pairs of vertices. \InputFile The first line contains the number of vertices $n~(1 \le n \le 100)$. The next $n$ lines of $n$ numbers describe the weighted matrix. Here $-1$ means no edges between vertices, and any non-negative number --- the presence of an edge of given weight. All elements on the main diagonal are always zero. \OutputFile Print the desired maximum shortest distance. \includegraphics{https://eolympusercontent.com/images/9f3o95tvb17md528j8hbmbdqlk.gif}