Даний неорієнтований граф без кратних ребер та петель. У ньому вже міститься деяка (можливо, нульова) кількість ребер. Можна за певну плату додавати нові ребра (плата своя для кожного ребра).

Потрібно за найменшу плату зробити граф зв'язним.

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

У першому рядку вхідних даних міститься одне ціле число \(𝑁\) (\(1 ≤ 𝑁 ≤ 50\)) – кількість вершин у вихідному графі.

Далі в \(𝑁\) рядках записано по \(𝑁\) невід'ємних цілих чисел у кожному ( \(𝑗\) -е число в \(𝑖\) -му рядку відповідає вартості додавання ребра, що з'єднує вершини \(𝑖\) і \(𝑗\) , 0 відповідає вже існуючому ребру, додатне число - неіснуючому), числа не перевищують 100. Матриця симетрична.

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

Вивести одне число – мінімально можливу вартість доповнення даного графа до зв'язного.

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

3
0 0 5 
0 0 0 
5 0 0

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

0