1 /* When all else is lost the future still remains. */ 2 #define rep(X,Y,Z) for(int X=(Y);X<(Z);X++) 3 #define drep(X,Y,Z) for(int X=(Y);X>=(Z);X--) 4 #define fi first 5 #define se second 6 #define mk(X,Y) make_pair((X),(Y)) 7 //head 8 #include <iostream> 9 #include <stdio.h>10 #include <queue>11 #include <algorithm>12 using namespace std;13 #define MAXN 11014 pair<int,pair<int,int> > wire[12010];15 int rp[MAXN];16 void init(){17     rep(i,0,MAXN) rp[i] = i;18     return ;19 }20 int f(int x){21     return rp[x] = (rp[x] == x) ? x : f(rp[x]);22 }23 int MST(int n){24     init();25     int ans = 0;26     rep(i,0,n){27         int val = wire[i].fi;28         int a = f(wire[i].se.fi);29         int b = f(wire[i].se.se);30         if(a == b) continue;31         rp[a] = min(a,b);32         rp[b] = min(a,b);33         ans += val;34     }35     return ans;36 }37 int DMST(int n){38     init();39     int ans = 0;40     drep(i,n-1,0){41         int val = wire[i].fi;42         int a = f(wire[i].se.fi);43         int b = f(wire[i].se.se);44         if(a == b) continue;45         rp[a] = min(a,b);46         rp[b] = min(a,b);47         ans += val;48     }49     return ans;50 }51 int main(){52     int T;53     scanf("%d",&T);54     rep(ca,1,T+1){55         int num;56         scanf("%d",&num);57         int cnt = 0;58         while(1){59             int w , u , v;60             scanf("%d %d %d",&u,&v,&w);61             if(!u&&!v&&!w) break;62             wire[cnt++] = mk(w,mk(u,v));63         }64         sort(wire,wire+cnt);65         int ansA = MST(cnt);66         int ansB = DMST(cnt);67         printf("Case %d: ",ca);68         if((ansA + ansB) % 2 == 0) printf("%d\n", (ansA + ansB) / 2);69         else printf("%d/2\n",ansA + ansB);70     }71     return 0;72 }