[USACO] 2-4-4 Bessie Come Home

/*
ID: 551100k1
LANG: C++
TASK: comehome
*/
#include<stdio.h>
#include<algorithm>
using namespace std;
char a[5],b[5];
int ma[300][300];
int main(){
    freopen("comehome.in","r",stdin);
    freopen("comehome.out","w",stdout);
    int n,x,i,j,k,ans=1e8;
    for(i=0;i<130;i++)
        for(j=0;j<130;j++)
            ma[i][j]=1e8;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%s%s%d",a,b,&x);
        ma[a[0]][b[0]]=min(ma[a[0]][b[0]],x);
        ma[b[0]][a[0]]=min(ma[b[0]][a[0]],x);
    }
    for(k=0;k<130;k++)
        for(i=0;i<130;i++)
            for(j=0;j<130;j++)
                if(i!=j && j!=k && i!=k && ma[i][k]+ma[k][j]<ma[i][j])
                    ma[i][j]=ma[i][k]+ma[k][j];
    for(i='A';i<='Y';i++)
        if(ma[i]['Z']<ans)
            ans=ma[i]['Z'],k=i;
    printf("%c %d\n",k,ans);
}