#include<iostream>
#include<cstdio>
using namespace std;
// build graph
const int V = 2500 + 5;
const int E = V*2;
int head[V], nxt[E], pnt[E], cost[E], e, n;
void add(int u,int v,int c){
    pnt[e] = v; cost[e] = c;
    nxt[e] = head[u]; head[u] = e; e++;
}
// tree dp
const int inf = ~0u>>2;
int mx[V], sd[V];
void dfs(int u,int f){
    mx[u]= 0; 
    sd[u] = 0;
    for(int i = head[u]; i!=-1; i=nxt[i]) {
        int v = pnt[i];
        if(v == f) continue;
        dfs(v,u);
        if(cost[i] + mx[v] > mx[u]) {
            sd[u] = mx[u];
            mx[u] = cost[i] + mx[v];
        }
        else if(cost[i] + mx[v] > sd[u])
            sd[u] = cost[i] + mx[v];
    }
}
int temp, flag;
void dfs1(int u,int f) {
//    cout<<"u: "<<u<<" "<<mx[u]<<" "<<sd[u]<<endl;
    if(mx[u] < temp) temp = mx[u];
    if(mx[u] > flag) flag = mx[u];
    for(int i = head[u]; i!=-1; i=nxt[i]) {
        int v = pnt[i];
        if(v == f) continue;
//        cout<<"v: "<<v<<" "<<mx[v]<<endl;
        if(mx[v] + cost[i] < mx[u])
            mx[v] = mx[u] + cost[i];
        else if(cost[i] + sd[u] > mx[v]){
            mx[v] = cost[i] + sd[u];
        }
        else if(cost[i] + sd[u] > sd[v]){
            sd[v] = cost[i] + sd[u];
        }
        dfs1(v,u);
    }
}
// main
int main(){
    int test;
    scanf("%d", &test);
    for(int _ = 1; _ <= test; _ ++){
        scanf("%d",&n);
        int u,v,c;
        //init
        for(int i=0;i<n;i++) head[i] = -1;
        e = 0;
        // input
        for(int i=1;i<n;i++) {
            scanf("%d%d%d",&u,&v,&c);
            add(u,v,c);
            add(v,u,c);
        }
        int ans = inf;
        for(int i=0;i<e;i+=2){
            int u = pnt[i], v = pnt[i^1], mn = cost[i], mx1, mx2;
            temp = inf;
            flag = 0;
            dfs(u,v); dfs1(u,v);
            mn += temp;
            mx1 = flag;
//            cout<<temp<<endl;
            temp = inf;
            flag = 0;
            dfs(v,u); dfs1(v,u);
            mn += temp;
            mx2 = flag;
            mn = max(max(mx1,mx2),mn);
//            cout<<temp<<endl;
            if(mn < ans) ans = mn; 
        }
        printf("Case %d: %d\n",_,ans);
    }
}