Авіаперельоти#1936
Головного інженера Петра попросили розробити нову модель літака для компанії "Ейр Бубундія". Було з'ясовано, що найскладнішим є вибір оптимального розміру паливного бака.
Головний картограф "Ейр Бубундії", Джон, склав детальну карту Бубундії. На цій карті він позначив витрати пального, необхідні для перельоту між кожною парою міст.
Петро хоче зробити розмір паливного бака якомога меншим, щоб літак міг долетіти з будь-якого міста в будь-яке інше (можливо, з дозаправками у містах по шляху).
У першому рядку задано кількість міст (1 \leq n \leq 1000) у Бубундії. Кожен з наступних рядків містить по чисел. -те число у -му рядку дорівнює витратам пального для перельоту з -го міста у -те. Всі числа невід'ємні та менші за 10^9. Гарантується, що для будь-якого -те число у -му рядку дорівнює .
Виведіть одне число — оптимальний розмір паливного бака.
Приклад 1