1208

#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <string>
#include <sstream>
#include <algorithm>

using namespace std;

struct Edge{
	int source,destination,weight;
};
//to keep track of parent and rank of union find
struct subset{
	int parent;
	int rank;
};
bool graph[100][100];
vector<Edge> edges;
subset* subsets;

bool cmp(Edge a,Edge b)
{
	return a.weight<b.weight;
}

int find(int node)
{
	if(subsets[node].parent!=node)
		return find(subsets[node].parent);
	return subsets[node].parent;
}

void Union(int x,int y)
{
	int xroot = find(x);
	int yroot = find(y);

	if(subsets[xroot].rank<subsets[yroot].rank)
		subsets[xroot].parent=yroot;
	else if(subsets[yroot].rank<subsets[xroot].rank)
		subsets[yroot].parent=xroot;
	else
	{
		subsets[yroot].parent=xroot;
		subsets[xroot].rank+=1;
	}

}
int main()
{
	int t,no_Of_Vertices,a;
	int counter,kase=1;
	stringstream ss;
	string s;
	Edge tEdge;
	Edge result[100];

	cin>>t;
	getchar();
	while(t--)
	{
		cin>>no_Of_Vertices;
		getchar();
		subsets = (subset*)malloc(sizeof(subset)*no_Of_Vertices);
		memset(graph,0,sizeof(graph));
		edges.clear();
		counter=0;
		for(int I=0;I<no_Of_Vertices;I++)
		{
			getline(cin,s);
			ss.clear();
			ss<<s;
			for(int K=0;K<no_Of_Vertices;K++)
			{
				ss>>a;
				if(ss.peek()==',')
					ss.ignore();
				if(a)
				{
					if(graph[I][K]==0)
					{
						graph[I][K]=graph[K][I]=1;
						tEdge.source=I;
						tEdge.destination=K;
						tEdge.weight=a;
						edges.push_back(tEdge);
					}
				}
			}
		}

		sort(edges.begin(),edges.end(),cmp);
		for(int I=0;I<no_Of_Vertices;I++)
		{
			subsets[I].parent=I;
			subsets[I].rank=0;
		}
		int i=0;
		while(counter<no_Of_Vertices-1)
		{
			tEdge = edges[i++];

			int x = find(tEdge.source);
			int y = find(tEdge.destination);

			if(x!=y)
			{
				result[counter++]=tEdge;
				Union(x,y);
			}
		}
		cout<<"Case "<<kase++<<":\n";
		char ch='A';
		for(int i=0;i<counter;i++)
		cout<<char(ch+result[i].source)<<"-"<<char(ch+result[i].destination)<<" "<<result[i].weight<<"\n";
	}

	return 0;
}