如果是树，那么一定选择树的直径的中点
套了个环？裸的想法显然是断开环，然后求所有树的直径的最小值
环套树dp的一般思路，先把环放到根，把环上点下面的子树dp出来，然后再处理环上的情况
设f[i]表示以i为根的子树向下延伸的最长链长度
我们把环上的点扩展一倍，用前缀和维护环上的边权
依次枚举断点，则对直径影响就是max(s[j]-s[i]+f[i]+f[j])
分别维护max(s[j]+f[j])和max(f[i]-s[i])
注意i≠j，所以我们还要维护一个次小值
type node=record
po,next,num:longint;
end;
link=record
loc:longint;
mx:int64;
end; var tree:array[..*,..] of link;
e:array[..] of node;
cut:array[..] of boolean;
a,b,p,fa:array[..] of longint;
v:array[..] of boolean;
f,s:array[..] of int64;
i,len,n,t,x,y,z:longint;
ll,ans,lin:int64;
l1,l2,tp:link; function max(a,b:int64):int64;
begin
if a>b then exit(a) else exit(b);
end; function min(a,b:int64):int64;
begin
if a>b then exit(b) else exit(a);
end; procedure add(x,y,z:longint);
begin
inc(len);
e[len].po:=y;
e[len].next:=p[x];
e[len].num:=z;
p[x]:=len;
end; procedure find(x:longint);
var i,y,h:longint;
begin
i:=p[x];
while i<>- do
begin
y:=e[i].po;
if not cut[i] then
begin
if fa[y]<> then
begin
h:=x;
while h<>y do
begin
inc(t);
a[t]:=h;
b[t]:=f[h];
h:=fa[h];
end;
inc(t);
a[t]:=h;
b[t]:=e[i].num;
break;
end
else begin
cut[i]:=true;
cut[i xor ]:=true;
fa[y]:=x;
f[y]:=e[i].num;
find(y);
end;
end;
if t<> then break;
i:=e[i].next;
end;
end; procedure dfs(x:longint);
var i,y:longint;
begin
v[x]:=true;
f[x]:=;
i:=p[x];
while i<>- do
begin
y:=e[i].po;
if not v[y] then
begin
dfs(y);
lin:=max(lin,f[y]+f[x]+e[i].num);
f[x]:=max(f[x],f[y]+e[i].num);
end;
i:=e[i].next;
end;
end; procedure update(var c:link; a:link; b:link);
begin
c.mx:=a.mx;
c.loc:=a.loc;
if c.mx<b.mx then
begin
c.loc:=b.loc;
c.mx:=b.mx;
end;
end; procedure build(i,l,r:longint);
var m:longint;
begin
if l=r then
begin
tree[i,].mx:=f[a[l]]+s[l];
tree[i,].loc:=l;
tree[i,].mx:=f[a[l]]-s[l];
tree[i,].loc:=l;
end
else begin
m:=(l+r) shr ;
build(i*,l,m);
build(i*+,m+,r);
update(tree[i,],tree[i*,],tree[i*+,]);
update(tree[i,],tree[i*,],tree[i*+,]);
end;
end; function ask(i,l,r,w,x,y:longint):link;
var m:longint;
s,s1,s2:link;
begin
if (x<=l) and (y>=r) then exit(tree[i,w])
else begin
m:=(l+r) shr ;
if x>m then exit(ask(i*+,m+,r,w,x,y));
if y<=m then exit(ask(i*,l,m,w,x,y));
s1:=ask(i*,l,m,w,x,y);
s2:=ask(i*+,m+,r,w,x,y);
update(s,s1,s2);
exit(s);
end;
end; begin
len:=-;
fillchar(p,sizeof(p),);
readln(n);
for i:= to n do
begin
readln(x,y,z);
add(x,y,z);
add(y,x,z);
end;
fa[]:=-;
find();
for i:= to t do
begin
v[a[i]]:=true;
a[i+t]:=a[i];
b[i+t]:=b[i];
end;
for i:= to *t do
s[i]:=s[i-]+b[i-];
for i:= to t do
dfs(a[i]);
build(,,*t);
ans:=;
for i:= to t do
begin
l1:=ask(,,*t,,i+,i+t);
l2:=ask(,,*t,,i+,i+t);
if l1.loc=l2.loc then
begin
ll:=;
if l1.loc>i+ then
begin
tp:=ask(,,*t,,i+,l1.loc-);
ll:=max(ll,l1.mx+tp.mx);
end;
if l2.loc<i+t then
begin
tp:=ask(,,*t,,l2.loc+,i+t);
ll:=max(ll,l2.mx+tp.mx);
end;
ans:=min(ans,max(ll,lin));
end
else ans:=min(ans,max(l1.mx+l2.mx,lin));
end;
writeln(ans/::);
end.