1 #include <iostream> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cstdio> 5 #include <cctype> 6 #include <cmath> 7 #include <algorithm> 8 #include <numeric> 9 10 #define typec int11 using namespace std;12 13 const typec inf = 0xffff;14 const int V = 105;15 int vis[V];16 typec lowc[V], 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;26         p = -1;27         for (j = 0 ; j < n; ++ j) {28             if (0 == vis[j] && minc > lowc[j]) {29                 minc = lowc[j];30                 p = j;31             }32         }33         if (inf == minc) return -1;34         res += minc;35         vis[p] = 1;36         for (j = 0 ; j < n; ++ j) {37             if (0 == vis[j] && lowc[j] > cost[p][j]) {38                 lowc[j] = cost[p][j];39             }40         }41     }42     return res;43 }44 45 int main () {46     int n;47     while (~scanf("%d", &n)) {48         if (!n) break;49         for (int i = 0 ; i < V; ++i) {50             for (int j = 0; j < V; ++ j) {51                 if (i == j) Map[i][j] = 0;52                 else Map[i][j] = inf;53             }54         }55 56         for (int i = 0 ; i < n * (n - 1) / 2; ++i) {57             int x, y, w, ok;58             scanf("%d%d%d%d", &x, &y, &w, &ok);59             if (!ok) {60                 Map[x - 1][y - 1] = Map[y - 1][x - 1] = min(Map[x][y], w);61             } else {62                 Map[x - 1][y - 1] = Map[y - 1][x - 1] = 0;63             }64         }65 66         cout << prim(Map, n) << endl;67     }68     return 0;69 }