#include<iostream>
#include<algorithm>
#define MAX 99999999
using namespace std;
int a[50][50];
typedef struct Node
{
    int v;
    int s;
    int e;    
    }Node;
Node num[50];
bool s[50];  
int dist[50];
int closet[50];
int cmp(const void *x,const void *y)
{
    Node *t1=(Node *)x;
    Node *t2=(Node *)y;
    if(t1->v!=t2->v)return t1->v-t2->v;
    if(t1->s!=t2->s)return t1->s-t2->s;
    return t1->e-t2->e;
    }  
int main()
{
    int i,j,k,t,n,c=1,min,len;
    scanf("%d",&t);
    while(t--)
    {
          scanf("%d",&n);
          for(i=1;i<=n;i++)
          {
              scanf("%d",&a[i][1]);
              if(a[i][1]==0)a[i][1]=MAX;
              for(j=2;j<=n;j++)
              {
                  scanf(" ,%d",&a[i][j]);
                  if(a[i][j]==0)a[i][j]=MAX;             
                  }             
              }    
          for(i=1;i<=n;i++)
          {
              dist[i]=a[1][i];
              closet[i]=1;
              s[i]=0;             
              }      
          s[1]=1;
          for(i=1;i<n;i++)
          {
              min=MAX;
              j=1;
              for(k=1;k<=n;k++)
              {
                  if(!s[k]&&dist[k]<min)
                  {
                     j=k;
                     min=dist[k];                                       
                     }             
                  }
              if(j==1)break;                
              s[j]=1;
              for(k=1;k<=n;k++)
              {
                  if(!s[k]&&a[j][k]<dist[k])
                  {
                     dist[k]=a[j][k];
                     closet[k]=j;                           
                     }             
                  }    
              }
          len=0;    
          for(i=2;i<=n;i++)
          {
              if(i>closet[i]){num[len].s=closet[i];num[len].e=i;}
              else {num[len].s=i;num[len].e=closet[i];}
              num[len].v=dist[i];
              len++;             
              }     
          qsort(num,len,sizeof(num[0]),cmp); 
          printf("Case %d:\n",c++);
          for(i=0;i<len;i++)
          {
              printf("%c-%c %d\n",num[i].s+'A'-1,num[i].e+'A'-1,num[i].v);              
              }                 
          }
    return 0;
    }