/*
题目大意：给n个点n-1条边的树，求删除哪条边时两个树中最大的直径与边权的乘积最小。
树的直径(Diameter)是指树上的最长简单路。
直径的求法：两遍BFS (or DFS)
若删除的边不是直径上的那么花费为max_len*wi
若删除的边是直径上的那么花费为max(dp[u][2],dp[v][2])*wi
*/
#pragma comment(linker, "/STACK:16777216")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std; const int maxn=;
int dep[maxn],ans[maxn],father[maxn],max_len;//ans下标对应边的编号
int dp[maxn][];//j=0存i节点的到子树中的最长路，j=1存次长路，j=2存直径
bool vis[maxn];//标记是否为直径上的点
inline int max(int a,int b){return a>b?a:b;}
struct node
{
int id,w,v;
node(int id=,int w=,int v=):id(id),w(w),v(v){}
};
vector<node> f[maxn]; void dfs_dep(int u,int pre)//找最长路
{
for(int i=;i<f[u].size();i++)
{
int v=f[u][i].v;
if(v==pre) continue;
dep[v]=dep[u]+;
father[v]=u;
dfs_dep(v,u);
}
return ;
} void dfs(int u,int pre)
{
dp[u][]=dp[u][]=dp[u][]=;
for(int i=;i<f[u].size();i++)
{
int v=f[u][i].v;
if(v==pre) continue;
dfs(v,u);
int temp=dp[v][]+;
if(temp>dp[u][])
{
dp[u][]=dp[u][];dp[u][]=temp;
}
else if(temp>dp[u][])
dp[u][]=temp;
dp[u][]=max(dp[u][],dp[v][]);//u在子树直径边上与不再直径边上
}
dp[u][]=max(dp[u][],dp[u][]+dp[u][]);//u在子树直径中与不再直径中
} void solve(int u,int pre)
{
for(int i=;i<f[u].size();i++)
{
int v=f[u][i].v,id=f[u][i].id,w=f[u][i].w;
if(v==pre) continue;
solve(v,u);
//在树的直径上
if(vis[u] && vis[v])
ans[id]=max(ans[id],w*dp[v][]);
else ans[id]=w*max_len;
}
} int main()
{
int t,i,n,icase=,a,b,w;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=;i<=n;i++) f[i].clear();
for(i=;i<n;i++)
{
scanf("%d%d%d",&a,&b,&w);
f[a].push_back(node(i,w,b));
f[b].push_back(node(i,w,a));
}
int st,ed=,temp;
dfs_dep(ed,-);
for(i=;i<=n;i++)
if(dep[ed]<dep[i]) ed=i;
dep[st=ed]=;
dfs_dep(st,-);
ed=st;
for(i=;i<=n;i++)
if(dep[ed]<dep[i]) ed=i;
max_len=dep[ed];
memset(vis,,sizeof(vis));
father[st]=-;temp=ed;
while(father[temp]!=-)
vis[temp]=true,temp=father[temp];
memset(ans,,sizeof(ans));
dfs(st,-);solve(st,-);
dfs(ed,-);solve(ed,-);
temp=;
for(i=;i<n;i++)
if(ans[i]<ans[temp]) temp=i;
printf("Case #%d: %d\n",++icase,temp);
}
return ;
}