/*
Nowadays, people have many ways to save money on accommodation when they are on vacation. One of these ways is exchanging houses with other people.
 
Here is a group of N people who want to travel around the world. They live in different cities, so they can travel to some other people's city and use someone's house temporary. Now they want to make a plan that choose a destination for each person. There are two rules should be satisfied:
 
All the people should go to one of the other people's city.
Two of them never go to the same city, because they are not willing to share a house.
They want to maximize the sum of all people's travel distance. The travel distance of a person is the distance between the city he lives in and the city he travels to. These N cities have N-1 highways connecting them. The travelers always choose the shortest path when traveling.
 
Given the highways' information, it is your job to find the best plan, that maximum the total travel distance of all people.
*/
#include<bits/stdc++.h>
 
using namespace std;
 
class graph{
    list<pair<int,int>> *l;
    int V;
 
public:
    graph(int n){
        V = n;
        l = new list<pair<int,int>> [V];
    }
 
    void addEdge(int u, int v, int weight, bool bidirectional=true){
        l[u].push_back(make_pair(v,weight));
 
        if(bidirectional){
            l[v].push_back(make_pair(u,weight));
        }
    }
 
    int dfs(int src, bool* visited, int* count_subtree, int &ans){
        visited[src] = true;
        count_subtree[src] = 1;
 
        for(auto x:l[src]){
            auto neighbour = x.first;
            if(!visited[neighbour]){
                count_subtree[src] += dfs(neighbour, visited, count_subtree, ans);
                int y = count_subtree[neighbour];
                ans += 2*min(y,V-y)*(x.second);
            }
        }
 
        return count_subtree[src];
    }
 
    void solve(){
        bool *visited = new bool[V]{0};
        int *count_subtree = new int[V]{0};
 
        int ans = 0;
        dfs(0, visited, count_subtree,ans);
 
        /*for(int i=0;i<V;i++){
            cout << i << " : " << count_subtree[i] << endl;
        }*/
 
        cout << ans << endl;
    }
 
};
 
int main(){
    int t,i=1;
    cin>>t;
    while(t--){
        int n;
        cin >> n;
 
        graph g(n);
 
        for(int i=0;i<n-1;i++){
            int x,y,z;
            cin>>x>>y>>z;
 
            g.addEdge(--x,--y,z);
        }
        cout << "Case #" << i++ << " ";
        g.solve();
    }
}
 

LyoKTm93YWRheXMsIHBlb3BsZSBoYXZlIG1hbnkgd2F5cyB0byBzYXZlIG1vbmV5IG9uIGFjY29tbW9kYXRpb24gd2hlbiB0aGV5IGFyZSBvbiB2YWNhdGlvbi4gT25lIG9mIHRoZXNlIHdheXMgaXMgZXhjaGFuZ2luZyBob3VzZXMgd2l0aCBvdGhlciBwZW9wbGUuCgpIZXJlIGlzIGEgZ3JvdXAgb2YgTiBwZW9wbGUgd2hvIHdhbnQgdG8gdHJhdmVsIGFyb3VuZCB0aGUgd29ybGQuIFRoZXkgbGl2ZSBpbiBkaWZmZXJlbnQgY2l0aWVzLCBzbyB0aGV5IGNhbiB0cmF2ZWwgdG8gc29tZSBvdGhlciBwZW9wbGUncyBjaXR5IGFuZCB1c2Ugc29tZW9uZSdzIGhvdXNlIHRlbXBvcmFyeS4gTm93IHRoZXkgd2FudCB0byBtYWtlIGEgcGxhbiB0aGF0IGNob29zZSBhIGRlc3RpbmF0aW9uIGZvciBlYWNoIHBlcnNvbi4gVGhlcmUgYXJlIHR3byBydWxlcyBzaG91bGQgYmUgc2F0aXNmaWVkOgoKQWxsIHRoZSBwZW9wbGUgc2hvdWxkIGdvIHRvIG9uZSBvZiB0aGUgb3RoZXIgcGVvcGxlJ3MgY2l0eS4KVHdvIG9mIHRoZW0gbmV2ZXIgZ28gdG8gdGhlIHNhbWUgY2l0eSwgYmVjYXVzZSB0aGV5IGFyZSBub3Qgd2lsbGluZyB0byBzaGFyZSBhIGhvdXNlLgpUaGV5IHdhbnQgdG8gbWF4aW1pemUgdGhlIHN1bSBvZiBhbGwgcGVvcGxlJ3MgdHJhdmVsIGRpc3RhbmNlLiBUaGUgdHJhdmVsIGRpc3RhbmNlIG9mIGEgcGVyc29uIGlzIHRoZSBkaXN0YW5jZSBiZXR3ZWVuIHRoZSBjaXR5IGhlIGxpdmVzIGluIGFuZCB0aGUgY2l0eSBoZSB0cmF2ZWxzIHRvLiBUaGVzZSBOIGNpdGllcyBoYXZlIE4tMSBoaWdod2F5cyBjb25uZWN0aW5nIHRoZW0uIFRoZSB0cmF2ZWxlcnMgYWx3YXlzIGNob29zZSB0aGUgc2hvcnRlc3QgcGF0aCB3aGVuIHRyYXZlbGluZy4KCkdpdmVuIHRoZSBoaWdod2F5cycgaW5mb3JtYXRpb24sIGl0IGlzIHlvdXIgam9iIHRvIGZpbmQgdGhlIGJlc3QgcGxhbiwgdGhhdCBtYXhpbXVtIHRoZSB0b3RhbCB0cmF2ZWwgZGlzdGFuY2Ugb2YgYWxsIHBlb3BsZS4KKi8KI2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgpjbGFzcyBncmFwaHsKICAgIGxpc3Q8cGFpcjxpbnQsaW50Pj4gKmw7CiAgICBpbnQgVjsKCnB1YmxpYzoKICAgIGdyYXBoKGludCBuKXsKICAgICAgICBWID0gbjsKICAgICAgICBsID0gbmV3IGxpc3Q8cGFpcjxpbnQsaW50Pj4gW1ZdOwogICAgfQoKICAgIHZvaWQgYWRkRWRnZShpbnQgdSwgaW50IHYsIGludCB3ZWlnaHQsIGJvb2wgYmlkaXJlY3Rpb25hbD10cnVlKXsKICAgICAgICBsW3VdLnB1c2hfYmFjayhtYWtlX3BhaXIodix3ZWlnaHQpKTsKCiAgICAgICAgaWYoYmlkaXJlY3Rpb25hbCl7CiAgICAgICAgICAgIGxbdl0ucHVzaF9iYWNrKG1ha2VfcGFpcih1LHdlaWdodCkpOwogICAgICAgIH0KICAgIH0KCiAgICBpbnQgZGZzKGludCBzcmMsIGJvb2wqIHZpc2l0ZWQsIGludCogY291bnRfc3VidHJlZSwgaW50ICZhbnMpewogICAgICAgIHZpc2l0ZWRbc3JjXSA9IHRydWU7CiAgICAgICAgY291bnRfc3VidHJlZVtzcmNdID0gMTsKCiAgICAgICAgZm9yKGF1dG8geDpsW3NyY10pewogICAgICAgICAgICBhdXRvIG5laWdoYm91ciA9IHguZmlyc3Q7CiAgICAgICAgICAgIGlmKCF2aXNpdGVkW25laWdoYm91cl0pewogICAgICAgICAgICAgICAgY291bnRfc3VidHJlZVtzcmNdICs9IGRmcyhuZWlnaGJvdXIsIHZpc2l0ZWQsIGNvdW50X3N1YnRyZWUsIGFucyk7CiAgICAgICAgICAgICAgICBpbnQgeSA9IGNvdW50X3N1YnRyZWVbbmVpZ2hib3VyXTsKICAgICAgICAgICAgICAgIGFucyArPSAyKm1pbih5LFYteSkqKHguc2Vjb25kKTsKICAgICAgICAgICAgfQogICAgICAgIH0KCiAgICAgICAgcmV0dXJuIGNvdW50X3N1YnRyZWVbc3JjXTsKICAgIH0KCiAgICB2b2lkIHNvbHZlKCl7CiAgICAgICAgYm9vbCAqdmlzaXRlZCA9IG5ldyBib29sW1ZdezB9OwogICAgICAgIGludCAqY291bnRfc3VidHJlZSA9IG5ldyBpbnRbVl17MH07CgogICAgICAgIGludCBhbnMgPSAwOwogICAgICAgIGRmcygwLCB2aXNpdGVkLCBjb3VudF9zdWJ0cmVlLGFucyk7CgogICAgICAgIC8qZm9yKGludCBpPTA7aTxWO2krKyl7CiAgICAgICAgICAgIGNvdXQgPDwgaSA8PCAiIDogIiA8PCBjb3VudF9zdWJ0cmVlW2ldIDw8IGVuZGw7CiAgICAgICAgfSovCgogICAgICAgIGNvdXQgPDwgYW5zIDw8IGVuZGw7CiAgICB9Cgp9OwoKaW50IG1haW4oKXsKICAgIGludCB0LGk9MTsKICAgIGNpbj4+dDsKICAgIHdoaWxlKHQtLSl7CiAgICAgICAgaW50IG47CiAgICAgICAgY2luID4+IG47CgogICAgICAgIGdyYXBoIGcobik7CgogICAgICAgIGZvcihpbnQgaT0wO2k8bi0xO2krKyl7CiAgICAgICAgICAgIGludCB4LHksejsKICAgICAgICAgICAgY2luPj54Pj55Pj56OwoKICAgICAgICAgICAgZy5hZGRFZGdlKC0teCwtLXkseik7CiAgICAgICAgfQogICAgICAgIGNvdXQgPDwgIkNhc2UgIyIgPDwgaSsrIDw8ICIgIjsKICAgICAgICBnLnNvbHZlKCk7CiAgICB9Cn0K

Mgo0CjEgMiAzCjIgMyAyCjQgMyAyCjYKMSAyIDMKMiAzIDQKMiA0IDEKNCA1IDgKNSA2IDU=

2
4
1 2 3
2 3 2
4 3 2
6
1 2 3
2 3 4
2 4 1
4 5 8
5 6 5