1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4  5 using namespace std; 6  7 #define MAX ‘Z‘+5 8 #define inf 99999999 9 10 int map[MAX][MAX],node[MAX],vis[MAX],n,path;11 12 void Prim()13 {14     int ans=‘A‘;15     node[ans]=0;16     vis[ans]=1;17     for(int k=‘A‘;k<(‘A‘+n);k++)18     {19         //cout<<k<<" "<<n<<endl;20         int minn=inf;21         for(int i=‘A‘;i<(‘A‘+n);i++)22         if(!vis[i]&&minn>node[i])23         {24             minn=node[i];25             ans=i;26         }27         //printf("%c %d\n",ans,minn);28         vis[ans]=1;29         path+=node[ans];30         //cout<<"      "<<path<<endl;31 32         for(int i=‘A‘;i<(‘A‘+n);i++)33         if(!vis[i]&&node[i]>map[ans][i])34         node[i]=map[ans][i];35     }36 }37 38 int main()39 {40     while(cin>>n&&n)41     {42         for(int i=‘A‘;i<=‘Z‘;i++)43         {44             node[i]=inf;45             vis[i]=0;46             for(int j=‘A‘;j<=‘Z‘;j++)47             map[i][j]=inf;48         }49         int N=n-1;50         char a,b;51         int t,dist;52         while(N--)53         {54             cin>>a>>t;55             while(t--)56             {57                 cin>>b>>dist;58                 if(map[a][b]>dist)59                 map[a][b]=map[b][a]=dist;60             }61         }62         path=0;63         Prim();64         cout<<path<<endl;65     }66     return 0;67 }