#include <bits/stdc++.h>
using namespace std;

#define mod 1000000007
#define fastIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define point(n) fixed<<setprecision(n)
#define endl '\n'
#define mem(a,val) memset(a,val,sizeof(a))
#define pb push_back 
typedef long long ll;
typedef unsigned long ul;
typedef unsigned long long ull;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
#define MOD 1000000000

struct pair_hash {
    template <class T1, class T2>
    size_t operator () (const pair<T1,T2> &p) const {
        auto h1 = hash<T1>{}(p.first);
        auto h2 = hash<T2>{}(p.second);
        return h1 ^ h2;  
    }
};

class Graph{
    public:
        int n;
        list<int> *adj;
        unordered_map<pair<int,int>,int,pair_hash> mp;
        vector<ll> count;
        bool visited[100001];
        Graph(int n){
            this->n=n;
            adj = new list<int>[n];
            count.resize(n,1);
        }
        void addEdge(int u, int v, int w){
            adj[u].push_back(v);
            adj[v].push_back(u);
            mp[{u,v}] = w;
            mp[{v,u}] = w;
        }
        ll getCountUtil(int node, bool visited[]){
            visited[node]=true;
            for(auto i: adj[node]){
                if(!visited[i]){
                    count[node] += getCountUtil(i,visited);
                }
            }
            return count[node];
        }
        void getCount(){
            memset(visited,false,sizeof(visited));
            for(int i=1;i<n;i++){
                if(!visited[i]){
                    count[i] = getCountUtil(i,visited);
                }
            }
        }
        ll getAnsUtil(int node, bool visited[]){
            visited[node]=true;
            ll sum=0;
            for(auto i: adj[node]){
                if(!visited[i]){
                    sum = sum + min(count[i],n-count[i]-1)*mp[{node,i}]*2 + getAnsUtil(i,visited);
                }
            }
            return sum;
        }
        ll getAns(){
            memset(visited,false,sizeof(visited));
            ll ans = 0; 
            for(int i=1;i<n;i++){
                if(!visited[i]){
                    ans += getAnsUtil(i,visited);
                }
            }
            return ans;
        }
};

int main()
{
    fastIO
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
    int t;
    cin>>t;
    for(int j=0;j<t;j++){
        int n;
        cin>>n;
        Graph G(n+1);
        for(int i=0;i<n-1;i++){
            int a,b,c;
            cin>>a>>b>>c;
            G.addEdge(a,b,c);
        }
        G.getCount();
        cout<<"Case #"<<j+1<<": "<<G.getAns()<<endl;
    }
    return 0;
}