Головного конструктора Петю попросили розробити нову модель літака для компанії <<Air Бубундія>>. Виявилося, що найскладніша частина полягає у підборі оптимального розміру паливного бака.

Головний картограф <<Air Бубундія>> Вася склав докладну карту Бубундії. На цій карті він зазначив витрату палива для перельоту між кожною парою міст.

Петя хоче зробити розмір бака мінімально можливим, для якого літак зможе долетіти від будь-якого міста до будь-якої іншої (можливо, з дозаправками в дорозі).

Формат вхідних даних

Перший рядок вхідного файлу містить натуральне число \(n\) (\(1 \le n \le 1000\)) --- число міст у Бубундії.

Далі йдуть \(n\) рядків по \(n\) чисел кожна. \(j\)-е число в \(i\)-му рядку дорівнює витраті палива при перельоті з \(i\)-ого міста до \(j\)-ого. Всі числа не менші за нуль і менші \(10^9\).

Гарантується, що для будь-якого \(i\) в \(i\)-му рядку \(i\)-е число дорівнює нулю.

Формат вихідних даних

Перший рядок вихідного файлу повинен містити одне число - оптимальний розмір бака.

Приклад вхідних даних

4
0 10  12  16
11 0  8   9
10 13 0   22
13 10 17  0

Приклад вихідних даних

10