/*
    題意：給出一棵樹，現可以移動一條邊，問怎么移動使得最長邊最小
            n <= 2500

    比賽時腦殘，一點想法都沒有
    賽后火車上，林老師提到枚舉最長路的邊，然后斷開，分別求子樹的重心連接起來，更新答案
    果然是NKU畢業的.Orz

    n那么小，我當時就否定了O(n)類的樹dp
    應該要想到 枚舉 + dfs 這樣子O(n^2)的復雜度！

    用兩個數組first[u],second[u]記錄點u為根的子樹的最長、次長的路
    第一次dfs，任意根
    第二次時，是調整整棵樹的根的位置，然后通過遞推計算出新根的first[],second[]，更新答案

 */
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<cmath>
#include<cstdlib>
#include<iostream>

using namespace std;

const int INF = 1000000000;
const int MAXN = 2510;

struct Edge
{
    int u, v, w;
    Edge *next;
    Edge(){}
    Edge(int _u , int _v , int _w)
    {
        u = _u;
        v = _v;
        w = _w;
    }
};

Edge *E[MAXN] , edges[MAXN*2] , *pE;

void add(int u , int v , int w)
{
    pE->u = u;
    pE->v = v;
    pE->w = w;
    pE->next = E[u];
    E[u] = pE++;
}

struct Pair
{
    int val , id;
};

Pair first[MAXN] , second[MAXN];

int longest , lid ,root;

void dfs1(int u ,int p)
{
    first[u].id = second[u].id = u;
    first[u].val = second[u].val = 0;
    for(Edge *it = E[u] ; it ; it = it->next)
    {
        int v = it->v , w = it->w;
        if(v == p)continue;
        dfs1(v,u);
        if( first[v].val + w >= first[u].val )// >=
        {
            second[u] = first[u];
            first[u].id = v;
            first[u].val = first[v].val + w;
        }
        else if(first[v].val + w > second[u].val)
        {
            second[u].id = v;
            second[u].val = first[v].val + w;
        }
    }
    if(longest < first[u].val + second[u].val)
    {
        longest = first[u].val + second[u].val;
        lid = u;
    }
    //printf("u  %d %d %d %d %d\n",u,first[u].val , first[u].id , second[u].val , second[u].id);
}

void dfs2(int u ,int p , int preDist)//從上往下，更改根的位置，遞推出新根的first[],second[]
{
    if( preDist != 0 )
    {
        if(first[p].id != u)
        {
            second[u] = first[u];///////////////////記得別丟掉了
            first[u].id = p;
            first[u].val = preDist + first[p].val;
        }
        else
        {
            if(second[p].val + preDist >= first[u].val)
            {
                second[u] = first[u];
                first[u].val = second[p].val + preDist;
                first[u].id = p;
            }
            else if(second[p].val + preDist >= second[u].val)
            {
                second[u].val = second[p].val + preDist;
                second[u].id = p;
            }
        }
    }

    if(longest > first[u].val)
    {
        longest = first[u].val;
        lid = u;
    }
    
    for(Edge *it = E[u] ; it ; it = it->next)
    {
        int v = it->v , w = it->w;
        if(v == p)continue;
        dfs2(v,u,w);
    }
}

int main()
{

#ifdef ONLINE_JUDGE
#else
    freopen("in", "r", stdin);
#endif

    int T ,t = 1;
    for(scanf("%d",&T) ; T-- ;)
    {
        int n , u , v, w;
        scanf("%d",&n);
        pE = edges;
        for(int i = 0 ; i < n;  i++)
        {
            E[i] = NULL;
        }
        for(int i = 1 ; i< n ; i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);
            add(v,u,w);
        }

        //longest    route
        longest = 0;
        dfs1(0,0);

        //printf("longest %d %d\n",longest,lid);

        int ans = longest , pos = lid , next;
        vector<Edge> VE;
        while( (next = first[pos].id) != pos)
        {
            VE.push_back( Edge( pos , next , first[pos].val - first[next].val ) );
            pos = next;
        }
        pos = lid , next = second[lid].id;
        if(pos != next)
        {
            VE.push_back(Edge(pos , next ,second[pos].val - first[next].val ));
            pos = next;
            while( (next = first[pos].id) != pos)
            {
                VE.push_back( Edge( pos , next , first[pos].val - first[next].val ) );
                pos = next;
            }
        }

        for(int i = 0 , size = VE.size() ; i < size ; i++)
        {
            u = VE[i].u , v = VE[i].v , w = VE[i].w;

           // printf("route %d %d %d\n",u,v,w);

            int _ans = 0;

            longest = 0;
            dfs1(u,v);
            _ans = max(_ans , longest);
            longest = INF;
            dfs2(u,v,0);
            int rootA = lid;

            longest = 0;
            dfs1(v,u);
            _ans = max(_ans , longest);
            longest = INF;
            root = v;
            dfs2(v,u,0);
            int rootB = lid;

            _ans = max(_ans , first[rootA].val + first[rootB].val + w);

            ans = min(ans , _ans);
        }

        printf("Case %d: %d\n",t++,ans);
    }
    return 0;
}