#include <cstring>
#include <iostream>
#include <stdlib.h>
using namespace    std;

struct Road
{
    char ss;
    char ee;
    int  ll;
};

Road R[395];
char F[26];
int i;

int KP(const void *a,const void *b)
{
    return (*(Road *)a).ll - (*(Road *)b).ll;
}

void setting()
{
    for(char k='A'; k<='Z'; k++)
    {
        F[k] = k;
    }
}

void reading(int N)
{
    int n = N;
    n--;
    i = 0;
    int M,LL;
    char SS,EE;
    while(n--)
    {
       cin>>SS>>M;
       while(M--)
       {
           cin>>EE>>LL;
           R[i].ss = SS;
           R[i].ee = EE;
           R[i].ll = LL;
           i++;
       }
    }
}

char finding(char p)
{
    if(p != F[p])
    {
        F[p] = finding(F[p]);
    }
    return F[p];
}

void putting(char x,char y)
{
    char xx = finding(x);
    char yy = finding(y);
    if(xx < yy)
    {
        F[yy] = xx;
    }
    else if(xx > yy)
    {
        F[xx] = yy;
    }
}

void minitree(int N,int i)
{
    int j;
    int num = 0;
    int total=0;
    for(j=0; j<i; j++)
    {
        if( finding(R[j].ss) != finding(R[j].ee) )
        {
            putting(R[j].ss, R[j].ee);
            total += R[j].ll;
            num++;
            if(num == N-1)
            {
                break;
            }
        }
    }
    cout<<total<<endl;
}

int main()
{
    int N,M;
    while(cin>>N&&N)
    {
        setting();
        reading(N);
        qsort(R,i,sizeof(R[0]),KP);
        minitree(N,i);
    }
    return 0;
}

• find it! (114) zzzjjjjjj 2011-01-07 18:03:56