#include<bits/stdc++.h>

using namespace std;

class Graph
{
    int V;
    list<pair<int,int>> *l;

public:
    Graph(int v)
    {
        V = v;
        l = new list<pair<int,int>> [V+1];
    }
    void addEdge(int u, int v,int cost)
    {
        l[u].push_back(make_pair(v,cost));
        l[v].push_back(make_pair(u,cost));
    }

    int dfsHelper(int node,bool *visited, int *count, int &ans)
    {
        //mark the node as visited
        visited[node] = true;
        count[node] = 1;

        for (auto nbr_pair:l[node])
        {
            int nbr = nbr_pair.first;
            int wt = nbr_pair.second;
            if (!visited[nbr])
            {
                // the count of node increases as we return from the children node
                count[node] += dfsHelper(nbr,visited,count,ans);

                //That count helps us to find the number of nodes of that component
                int nx = count[nbr];
                int ny = V - nx;
                // ans is added to the variable ans
                ans += 2*min(nx,ny) * wt;
            }
        }

        // Just before leaving the node parent
        return count[node];
    }
    int dfs()
    {
        /*
        If you want to dynamically allocate an array of booleans, you need to do

            bool *arr = new bool[10];
            You have to specify the array size.


        The syntax for static allocation is

            bool arr[10];
        */

        bool *visited = new bool[V+1];
        int *count = new int[V+1];

        for(int i=1;i<V+1;i++)
        {
            visited[i] = false;
            count[i] = 0;
        }
        int ans = 0;
        dfsHelper(1,visited,count,ans);
        return ans;
    }
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    int i=1;
    while (i<=t)
    {
        int n;
        cin>>n;
        Graph g(n);
        for (int j=1;j<=n-1;j++)
        {
            int x,y,z;
            cin>>x>>y>>z;
            g.addEdge(x,y,z);
        }
        int req = g.dfs();
        cout<<"Case #"<<i<<": "<< req<<endl;
        i += 1;
    }
}