/*#include
     
      using namespace std;int data[100][100];int d[100];//存放当前的s到各点最小距离；int v[100];//标记是否用过；int sum;const int maxint=99999;void shuru(int n){    int a,b,c;    for(int i=1;i<=100;i++)//初始化data[][]；        for(int j=1;j<=100;j++)        data[i][j]=maxint;    for(int i=1;i<=n;i++)//初始化d[]；使得其值为maxint;        d[i]=maxint;        while(cin>>a>>b>>c)        {            data[a][b]=c;//无相边；            data[b][a]=c;        }}void prim(int n){    d[1]=0;sum=0;    memset(v,0,sizeof(v));    for(int i=1;i<=n;i++)    {        int min=maxint;        int k=0;        for(int j=1;j<=n;j++)        {            if(!v[j]&&d[j]<=min)            {                min=d[j];                k=j;            }        }        sum=sum+min;        v[k]=1;//标记已存的顶点标号；        for(int g=1;g<=n;g++)            //更新d[];由于s的集合多了一个k顶点，下一步比较未标记的顶点                到s的最小距离d【】时，只需要原来的d[j]和data[k][j]比较;            if(!v[g]&&d[g]>data[k][g])                d[g]=data[k][g];    }    cout<<"一共需要的最小权值为：    "<
      
       <
       
        >n>>m;    shuru(n);    for(int j=1;j<=n;j++)        {for(int i=1;i<=n;i++)            cout<
        
         <<"     ";    cout<
         
          using namespace std;int data[101][101];int d[101];//存放当前的最小距离；int v[101];//标记是否用过；int sum;const int maxint=99999;void shuru(int n){    int a,b,c;    char as,nn;    memset(data,0,sizeof(data));    memset(d,0,sizeof(d));    for(int i=1;i<=100;i++)//初始化data[][]；        for(int j=1;j<=100;j++)        data[i][j]=maxint;    for(int i=1;i<=n;i++)//初始化d[]；使得其值为maxint;        d[i]=maxint;    for(int i=1;i
          
           >as>>a; while(a--) {cin>>nn>>b;data[as-'A'+1][nn-'A'+1]=b; data[nn-'A'+1][as-'A'+1]=b;} }}void prim(int n){ d[1]=0;sum=0; memset(v,0,sizeof(v)); for(int i=1;i<=n;i++) { int min=maxint; int k=1; for(int j=1;j<=n;j++) { if(!v[j]&&d[j]<=min) { min=d[j]; k=j; } } sum=sum+min; v[k]=1; for(int g=1;g<=n;g++) if(!v[g]&&d[g]>data[k][g]) d[g]=data[k][g]; } cout<
           
            <
            
             >n&&n) { shuru(n); prim(n); } return 0;}*/#include
             
              using namespace std;int d[100];//用来记录边的一顶点；int u[100];//另一顶点；int w[100];//权值；int p[100];//并查集是使用；int g[100];//给边编号；int sum;//统计权值最小和；int shuru(int n)//m表示一共的边数；{ int a,b,dd=1; char as,nn; for(int i=1;i
              
               >as>>a; while(a--) {cin>>nn>>b; u[dd]=nn-'A'+1; w[dd]=b; d[dd]=as-'A'+1; dd++;} } return --dd;}int cmp(const void * a,const void * b){ return w[*(int *)a]-w[*(int *)b];//排序比较，权值从小到大}int find(int x){ return x==p[x]?x:p[x]=find(p[x]);}void kruskal(int n,int m){ sum=0; memset(p,0,sizeof(p)); memset(g,0,sizeof(g)); for(int i=1;i<=n;i++)//初始化并查集，每个顶点都是一个集合； p[i]=i; for(int i=1;i<=m;i++)//给边编号； g[i]=i; qsort(g,m+1,sizeof(g[1]),cmp);/* for(int i=1;i<=m;i++) cout<
               
                <<" "; cout<
                
                 >n&&n) { memset(d,0,sizeof(d)); memset(u,0,sizeof(u)); memset(w,0,sizeof(w)); m=shuru(n); kruskal(n,m); } return 0;}