package day12_1406;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class well_project {
static int n;
static int value;
static int[][] map;
static int[] parent, key;
static boolean[] visit;
private static int minKey(){
int min = Integer.MAX_VALUE; int min_idx = -1;
for(int i = 0; i < n; i++){
if(!visit[i] && min > key[i]){
min = key[i];
min_idx = i;
}
}
return min_idx;
}
private static void prim(){
key[0] = 0;
for(long i = 0; i < n; i++){
int node = minKey();
visit[node] = true;
for(int j = 0; j < n; j++){
if(!visit[j] && map[node][j] != 0 && map[node][j] < key[j]){
key[j] = map[node][j];
}
}
}
}
static boolean isValidEdge(int u, int v, boolean[] inMST)
{
if (u == v)
return false;
if (inMST[u] == false && inMST[v] == false)
return false;
else if (inMST[u] == true && inMST[v] == true)
return false;
return true;
}
private static void primv2(){
boolean []inMST = new boolean[n];
inMST[0] = true;
int edge_count = 0, mincost = 0;
while (edge_count < n - 1)
{
// Find minimum weight valid edge.
int min = Integer.MAX_VALUE, a = -1, b = -1;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (map[i][j] < min)
{
if (isValidEdge(i, j, inMST))
{
min = map[i][j];
a = i;
b = j;
}
}
}
}
if (a != -1 && b != -1)
{
edge_count++;
mincost = mincost + min;
inMST[b] = inMST[a] = true;
}
}
value = mincost;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
try {
System.setIn(new FileInputStream("D:\\Trainee\\SRV_training\\src\\day12_1406\\WellProject.txt"));
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
Scanner sc = new Scanner(System.in);
int testcase = sc.nextInt();
for(int tc = 1; tc <= testcase; tc++){
n = sc.nextInt();
map = new int[n][n];
parent = new int[n]; key = new int[n];
visit = new boolean[n];
for(int i = 0; i < n; i++){
key[i] = Integer.MAX_VALUE;
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
map[i][j] = sc.nextInt();
}
}
value = 0;
primv2();
// for(int i = 0; i < n; i++){
// value += key[i];
// }
System.out.println("Case #" + tc);
System.out.println(value);
}
}
}