Задача Минимальное остовное дерево ≡

Условие

Вам дан связный, взвешенный, неориентированный граф, ваша задача подсчитать сумму ребер его минимального остовного дерева.

Формат входных данных

В первой строке натуральное число N - размерность матрицы смежности. Далее идет матрица смежности.

Формат выходных данных

Число - сумма ребер минимального остовного дерева

Ограничения

2 ≤ N ≤ 1000

Примеры тестов

2
0 3
3 0

3

4
0 1 0 3
1 0 4 2
0 4 0 0
3 2 0 0

7