Flights
The Chief Engineer Peter was asked to develop a new model of aircraft for the company "Air Bubundiya". It was found that the hardest part is choosing the optimal size of the fuel tank.
The Chief Cartographer of "Air Bubundiya" John has made a detailed map of Bubundiya. On this map he marked the fuel consumption for the flight between each pair of cities.
Peter wants to make the size of fuel tank as small as possible, so that the aircraft can fly from any city to any other(possibly with refueling in cities on the way) .
Input
The first line contains the number of cities n (1 ≤ n ≤ 1000) in Burbundiya. Each of the next n lines contains n numbers. The j-th number in the i-th line equals to fuel consumption during the flight from i-th city to the j-th. All numbers are nonnegative and less than 10^9. It is known that for any i the number at the i-th line and the i-th position is zero.
Output
Print one number - the optimal size of the fuel tank.
