favorite We need a little bit of your help to keep things running, click on this banner to learn more

Shortest paths - interesting graph problems

Trees in the garden

The Central Garden in Olympia country is so big that one gardener can not maintain it. It was decided to divide the garden into two parts. Certain trees will be assigned to the first part, and the rest to the second. One part of the garden can remain empty.

Between each pair of trees in the garden the roads are trodden. When gardeners go from one tree to another, they go along the road directly connecting the two trees. The length of the path is the same when moving in both directions.

To simplify the work of gardeners, it was decided to divide the garden so that the length of the longest path between a pair of trees belonging to the same part is minimal.

Write a program that according to the information about the lengths of the paths between all pairs of trees, finds the length of the longest road between the trees from one part of the garden, when the garden has optimal division into two parts.


The first line contains one integer n (2n1000) - the number of trees in the garden. Each i-th from the next n - 1 lines contains n - i numbers that gives the the road lengths between the i-th tree and trees from i + 1 to n-th. All numbers are non negative integers, not greater than 106.


Print one integer - the minimum length of the longest road between the trees in one part of the garden for all possible partitions of the garden.

Time limit 1 second
Memory limit 128 MiB
Input example #1
1 5
Output example #1
Author Vladimir Tkachuk
Source 2007 XX All-Ukrainian Informatics Olympiad, Kremenchuk, April 10 - 16, Round 1