Minimum Water Irrigation

You are given N gardens and a matrix W of size N×N where W[i][j] represents the amount of water required to travel from garden i to garden j. A value of -1 indicates that there is no direct path between the two gardens. Your task is to determine the minimum amount of water needed to irrigate (connect) all the gardens, assuming you can start irrigation from any garden.

This problem can be modeled by finding the Minimum Spanning Tree (MST) of a graph. If an MST covering all gardens exists, output its total cost. Otherwise, if not all gardens are reachable, output -1.

The underlying algorithm involves a classic MST construction using Prim's algorithm. Note that the formula for the MST cost is given by:

\( \text{MST Cost} = \sum_{e \in T} \text{cost}(e) \)

If the graph is disconnected, report -1.

inputFormat

The first line contains an integer N representing the number of gardens. The next N lines each contain N space-separated integers forming the matrix W, where W[i][j] is the water required to go from garden i to garden j (with -1 indicating no direct connection).

outputFormat

Output a single integer which is the minimum amount of water required to irrigate all gardens. If it is impossible to connect all gardens, output -1.## sample

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

6