#include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<algorithm>

 #include<iostream>

 using namespace std;

 void setIO(const string& s) {

     freopen((s + ".in").c_str(), "r", stdin);

     freopen((s + ".out").c_str(), "w", stdout);

 }

 template<typename Q> Q read(Q& x) {

     static char c, f;

     for(f = ; c = getchar(), !isdigit(c); ) if(c == '-') f = ;

     for(x = ; isdigit(c); c = getchar()) x = x *  + c - '';

     if(f) x = -x;

     return x;

 }

 template<typename Q> Q read() {

     static Q x; read(x); return x;

 }

 const int N =  + ;

 int main() {

 #ifdef DEBUG

     freopen("in.txt", "r", stdin);

     freopen("out.txt", "w", stdout);

 #endif

     static int du[N], mx[N];

     int T = read<int>();

     for(int cas = ; cas <= T; cas++) {

         memset(du, , sizeof du);

         memset(mx, , sizeof mx);

         int ans = ;

         int u, v, w, n = read<int>();

         for(int i = ; i < n; i++) {

             read(u), read(v), read(w);

             du[u] += w, du[v] += w;

             mx[u] = max(mx[u], w);

             mx[v] = max(mx[v], w);

             ans += w;

         }

         for(int u = ; u <= n; u++) {

             if((mx[u] << ) <= du[u]) ans -= du[u] >> ;

             else ans -= du[u] - mx[u];

         }

         printf("Case #%d: %d\n", cas, ans);

     }

     return ;

 }