Minimum Spanning Tree using Kruskal's Algorithm

You are given an undirected weighted graph represented by its adjacency matrix. Your task is to compute the weight of its Minimum Spanning Tree (MST) using Kruskal's algorithm.

The graph has n nodes (numbered from 0 to n - 1). The value at the i^th row and j^th column of the matrix represents the weight of the edge connecting node i and node j. A weight of 0 indicates that there is no edge between those nodes.

Recall that for a given graph, the weight of its Minimum Spanning Tree is defined as the sum of the weights of the selected edges that connect all vertices with the minimum possible total weight and without forming any cycles. In mathematical terms, if \(E'\) is the set of edges chosen for the MST and \(w(e)\) is the weight of edge \(e\), then the total MST weight is given by:

\( \text{MST extunderscore weight} = \sum_{e \in E'} w(e) \)

You are required to read the input from stdin and output the result to stdout.

inputFormat

The first line contains a single integer n which represents the number of nodes in the graph. Each of the following n lines contains n integers, where the j^th integer on the i^th line represents the weight of the edge between nodes i and j. A weight of 0 indicates no direct edge.

outputFormat

Output a single integer, which is the total weight of the Minimum Spanning Tree of the graph.

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

6