绝不严谨推理，只管大胆胡猜。
题意就是任意删掉一条边，再添加一条等长的边，保证仍然是一棵树的前提下最小化新树的直径。
显然要从原树的直径上删。如果不是的话新树的直径没变，不优。
$n\le 5000$直接暴力枚举直径上的边。删掉后直径要么是分裂出的两棵树的直径，要么是连边后产生的新直径。
两棵树合并后，新树的直径两端点一定是在这两棵树四个直径端点里取到。
再对这两棵树求直径，在这两条直径上挑两个点连起来一定最优。
至于挑哪两个点，当然是中点了。
于是$O(n^2)$就能水过去了。
还有个$O(n)$的做法， 过于神仙，告辞。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define maxn 5005
#define inf 0x3f3f3f3f
using namespace std;
inline int read(){
int x=0,y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}
struct edge{
int pre,fr,to,l;
bool vis;
}e[maxn<<1];
int h[maxn],a[maxn],deep[maxn],edg[maxn],fa[maxn],num=1,root,ma;
inline void add(int from,int to,int l){
e[++num]=(edge){h[from],from,to,l,0};
h[from]=num;
}
void dfs(int node,int len=0){
if(len>ma)ma=len,root=node;
for(register int i=h[node],x;i;i=e[i].pre){
if(e[i].vis)continue;
x=e[i].to;
if(x==fa[node])continue;
fa[x]=node,a[x]=i;
dfs(x,len+e[i].l);
}
}
pair<int,int> get_diameter(int rt){
int node;
fa[rt]=0,ma=-1,dfs(rt),fa[node=root]=0,ma=-1,dfs(node);
return make_pair(node,root);
}
int main(){
int n=read(),cnt=0,ans=inf;
for(register int i=1,x,y,z;i<n;++i)x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z);
pair<int,int>o=get_diameter(1);
while(o.second!=o.first)edg[++cnt]=a[o.second],o.second=fa[o.second];
for(register int i=1;i<=cnt;++i){
e[edg[i]].vis=e[edg[i]^1].vis=1;
int all=0,mi=inf,_mi=inf,ma1,ma2;
o=get_diameter(e[edg[i]].fr),ma1=ma;
if(o.first==o.second)mi=0;
while(o.first!=o.second)all+=e[a[o.second]].l,mi=min(mi,max(ma-all,all)),o.second=fa[o.second];
all=0,o=get_diameter(e[edg[i]].to),ma2=ma;
if(o.first==o.second)_mi=0;
while(o.first!=o.second)all+=e[a[o.second]].l,_mi=min(_mi,max(ma-all,all)),o.second=fa[o.second];
ans=min(ans,max(mi+_mi+e[edg[i]].l,max(ma1,ma2)));
e[edg[i]].vis=e[edg[i]^1].vis=0;
}
printf("%d\n",ans);
}
