Minimum Communication Links Cost

You are given a distributed database system with N nodes. The cost of installing a bidirectional communication link between any two nodes is provided in a cost matrix. Your task is to determine the minimum total cost required to establish a network such that any update can be propagated between any two nodes via at most one intermediate node.

This can be achieved by constructing a Minimum Spanning Tree (MST) of the graph defined by the nodes and their link establishment costs. In an MST, the sum of weights (costs) of the selected links is minimized, ensuring full connectivity among nodes.

Note: All links are bidirectional and each entry in the cost matrix, \(c_{ij}\), represents the cost of a direct link between node \(i\) and node \(j\). The diagonal elements are 0.

inputFormat

The first line contains an integer N representing the number of nodes.

The next N lines each contain N space-separated integers, where the j-th integer on the i-th line represents the cost \(c_{ij}\) of establishing a direct link between node \(i\) and node \(j\).

outputFormat

Output a single integer representing the minimum total cost required to establish the necessary communication links.

4
0 2 6 8
2 0 4 7
6 4 0 3
8 7 3 0

9