天津的B题，这是一个枚举+treedp的题目，当时没有时间写了，补一下。
不知道为什么TOJ 和 HOJ 都还没与贴出来。

简单说一下做法吧，我们定义一棵树任意两点（一个点就是自己和自己）的最长距离是树的直径D。
一个点对于任意一个点到他的距离最大的和其他点相比最小，那么这个点就是树的树心，那个最小的最大距离。
就是树的半径R。
在这个题目中我们要做的就是枚举要拆的边，分别求拆后形成的两棵树的D，R。
最后打答案就是 MIN( R1[i]+R2[i]+L[i],  D1[i],   D2[i]); i取遍所有的边，L[i]表示的是边的长度， 1，2分别就指剩下的两棵树。 

求R和D要两次treedp
第一次求每个点从他的儿子节点出发的最长距离和次长距离。
第二次求每个点从他出发的所有点的最长距离和次长距离，在这里就是要把从他父亲节点出发的情况加进来。

using namespace std;
const int inf=1000000000;

struct { int l, v; } dp[2505][2];
struct { int v, l, next; } e[2505];
int head[2505], num;
void add(int a, int b, int c)
{
 e[num].v=b; e[num].l=c;
 e[num].next=head[a]; head[a]=num++;
}

void dfs1(int root, int x)
{
    dp[x][0].v=x; dp[x][0].l=0;
 dp[x][1].v=x; dp[x][1].l=0;
 for (int i=head[x]; i!=-1; i=e[i].next)
 {
  int son=e[i].v, len=e[i].l;
  if (son==root) continue;
  dfs1(x, son);
  if (dp[son][0].l+len>dp[x][0].l)
  {
   dp[x][1]=dp[x][0];
   dp[x][0].l=dp[son][0].l+len;
   dp[x][0].v=son;
  }
  else
  if (dp[son][0].l+len>dp[x][1].l)
  {
   dp[x][1].l=dp[son][0].l+len;
   dp[x][1].v=son;
  }
 }
 //printf("%d %d %d %d %d\n", x, dp[x][0].v, dp[x][0].l, dp[x][1].v, dp[x][1].l);
}

int radius, diameter;
void dfs2(int root, int x)
{
 radius=min(radius, dp[x][0].l);
    diameter=max(diameter, dp[x][0].l+dp[x][1].l);
 int tmp;
 for (int i=head[x]; i!=-1; i=e[i].next)
 {
  int son=e[i].v, len=e[i].l;
  if (son==root) continue;
  if (dp[x][0].v!=son)
  {
   tmp=dp[x][0].l+len;
  }
  else
  {
   tmp=dp[x][1].l+len;
  }
  
  if (tmp>dp[son][0].l)
  {
   dp[son][1]=dp[son][0];
   dp[son][0].l=tmp;
   dp[son][0].v=x;
  }
  else
  if (tmp>dp[son][1].l)
  {
   dp[son][1].l=tmp;
   dp[son][1].v=x;
  }
  dfs2(x, son);
 }
}


int slove(int y, int x, int l)
{
 diameter=0;
 
 dfs1(y, x);
 radius=inf;
 dfs2(y, x);
    l+=radius;
 
 dfs1(x, y);
 radius=inf;
 dfs2(x, y);
    l+=radius;
 
 return max(l, diameter);
}

int main()
{
    int test, a, b, c, n, edge[2505][3]; scanf("%d", &test);
 while (test--)
 {
  memset(head, -1, sizeof(head)); num=0;
  scanf("%d", &n);
  if (n==1) { puts("0"); continue; }
  for (int i=1; i<n; i++)
  {
   scanf("%d %d %d", &a, &b, &c);
   add(a, b, c);
   add(b, a, c);
      edge[i][0]=a; edge[i][1]=b; edge[i][2]=c;
  }
        
  int ans=inf;
  for (int i=1; i<n; i++)
  {
   ans=min(ans, slove(edge[i][0], edge[i][1], edge[i][2]));
  }
  printf("%d\n", ans);
 }
 return 0;
}