1 #include <iostream> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cstdio> 5 #include <cmath> 6 #include <cctype> 7 #include <algorithm> 8 #include <numeric> 9 10 #define typec int11 using namespace std;12 13 const typec inf = 0xffff;14 const int V = 35;15 int vis[V]; typec lowc[V];16 int Map[V][V];17 18 typec prim (typec cost[][V], int n) {19     int i, j, p;20     typec minc, res = 0;21     memset(vis, 0, sizeof (vis));22     vis[0] = 1;23     for (i = 1; i < n; ++ i) lowc[i] = cost[0][i];24     for (i = 1; i < n; ++ i) {25         minc = inf; p = -1;26         for (j = 0 ; j < n; ++ j) {27             if ( 0 == vis[j] && minc > lowc[j]) {28                 minc = lowc[j]; p = j;29             }30         }31         if (inf == minc) return -1;32         res += minc; vis[p] = 1;33         for (j = 0 ; j < n; ++ j) {34             if (0 == vis[j] && lowc[j] > cost[p][j]) {35                 lowc[j] = cost[p][j];36             }37         }38     }39     return res;40 }41 42 43 int main () {44     int n;45     while (~scanf("%d", &n)) {46         if (n == 0) break;47         for (int i = 0 ; i < n; ++ i) {48             for (int j = 0 ;j < n; ++ j) {49                 if (i == j) Map[i][j] = 0;50                 else Map[i][j] = inf;51             }52         }53 54         for (int i = 0 ; i < n - 1; ++ i) {55             char s_c; int e_n;56             cin >> s_c >> e_n;57             for (int j = 0 ; j < e_n; ++ j) {58                 char e_c; int w;59                 cin >> e_c >> w;60                 Map[s_c - ‘A‘][e_c - ‘A‘] = Map[e_c - ‘A‘][s_c - ‘A‘] = min(Map[s_c - ‘A‘][e_c - ‘A‘], w);61             }62         }63 64         cout << prim(Map, n) << endl;65     }66     return 0;67 }