矩阵里的生成树

难度：T2

【知识点：Prim最小生成树】

前置知识：本单元此前讲解的状态、边界与实现。

题目描述

用一个对称矩阵给出无向图，求连通所有顶点的最小生成树费用。矩阵中的无边标记不是负费用。

输入格式

输入$n$，随后$n$行$n$列对称矩阵。非负整数表示无向边费用，-$1$表示无边，主对角线为$0$。

规则说明

生成树是选取原图中的一部分边，使所有顶点连通且不形成环；费用为选中边的权值之和。最小生成树是在所有生成树中总费用最小的一个。只有一个顶点时，不选边即可形成生成树，费用为 $0$。

输出格式

输出最小生成树费用；无法连通输出IMPOSSIBLE。

数据范围

$1\le n\le 500$，存在的边费用≤$10^9$。

样例输入

1
0

样例输出

0

样例输入 2

3
0 2 5
2 0 3
5 3 0

样例输出 2

5

样例说明 2

连接 $1$—$2$ 和 $2$—$3$，总费用为 $2+3=5$。