Остов плотного графа

Полный граф задан матрицей весов $n \times n$. Найдите вес минимального остовного дерева.

В первой строке $n$ ($1 \le n \le 1000$). В каждой из следующих $n$ строк — $n$ чисел: $w_{ij}$ ($0 \le w_{ij} \le 10^9$) — вес ребра между $i$ и $j$. Матрица симметрична, на диагонали нули.

Выведите вес минимального остовного дерева.