#include <stdio.h>
#include <iostream>
#include <fstream>
using namespace std;

#define Max 100000


int n;
int a[30][30];

int mark[100];

struct edge{
	int start,end;
	int cost;
} p[1000];
int pn;

int min(int s,int t){
	if(s>t)return t;
	else return s;
}
int max(int s,int t){
	if(s>t)return s;
	else return t;
}

int cmp(const void *a1,const void *a2){
	edge p=*(edge*)a1;
	edge q=*(edge*)a2;
	if(p.cost==q.cost){
		int pmin=min(p.start,p.end);
		int qmin=min(q.start,q.end);
		if(pmin!=qmin){
			return (pmin-qmin);
		}else{
			int pmax=max(p.start,p.end);
			int qmax=max(q.start,q.end);
			return (pmax-qmax);
		}
	}
	return (p.cost-q.cost);
}


void prim(int start){
	memset(mark,0,sizeof(mark));
	mark[start]=1;
	int d[1000];
	int s[100];     //父节点
	s[0]=-1;
	for(int i=1;i<n;i++){
		d[i]=a[start][i];
		s[i]=start;
	}
	for(i=1;i<n;i++){
		int node=-1;
		int min=Max;
		for(int j=1;j<n;j++){
			if(mark[j]==0&&d[j]<min){
				min=d[j];
				node=j;
			}
		}
		p[pn].start=s[node];p[pn].end=node;p[pn].cost=min;
		pn++;
		for(j=1;j<n;j++){
			if(mark[j]==0&&a[node][j]<d[j]){
				d[j]=a[node][j];
				s[j]=node;
			}
		}
		mark[node]=1;
	}
	return;

}

void main(){
//	ifstream cin("data.txt");
//	freopen("data.txt","r",stdin);
	int testcase;
	scanf("%d",&testcase);
	for(int i=0;i<testcase;i++){
		scanf("%d",&n);
		for(int j=0;j<n;j++){
			for(int k=0;k<n-1;k++){
				scanf("%d,",&a[j][k]);
			}
			scanf("%d",&a[j][n-1]);
		}
		//prim(0);
		for(j=0;j<n;j++){
			for(int k=0;k<n;k++){
				if(a[j][k]==0)a[j][k]=Max;
			}
		}

		pn=0;
		prim(0);
		qsort(p,pn,sizeof(p[0]),cmp);
		cout<<"Case "<<i+1<<":"<<endl;
		for(j=0;j<pn;j++){
		//	cout<<p[j].start<<" "<<p[j].end<<" "<<p[j].cost<<endl;
			int xmin=min(p[j].start,p[j].end);
			int xmax=max(p[j].start,p[j].end);
			char start=xmin+'A';char end=xmax+'A';
			cout<<start<<"-"<<end<<" "<<p[j].cost<<endl;
		}
	}

}