Minimum Cost to Connect All Points

In this problem, you are given a complete weighted graph represented by an n×n cost matrix. Your task is to find the minimum cost required to connect all points (i.e., the minimum spanning tree cost). Formally, given an integer $n$ and a cost matrix $C$, where $C[i][j]$ represents the cost to connect point $i$ and point $j$, find the minimum total cost such that all points become connected.

One efficient solution uses Prim's algorithm.

Formally, you are to compute $$\min\sum_{(u,v)\in T}C[u][v],$$ where $T$ is a spanning tree of the complete graph with vertices $\{0,1,\ldots,n-1\}$.

inputFormat

The input is read from standard input (stdin) and has the following format:

First line: a single integer $n$ denoting the number of points.

Next $n$ lines: each line contains $n$ space-separated integers representing the cost matrix. The $j$-th integer in the $i$-th line denotes $C[i][j]$.

outputFormat

Output to standard output (stdout) a single integer that is the minimum cost to connect all points.## sample

3
0 1 2
1 0 3
2 3 0

3