Description
小T打算在城市C开设一家外送快餐店。送餐到某一个地点的时间与外卖店到该地点之间最短路径长度是成正比的，小T希望快餐店的地址选在离最远的顾客距离最近的地方。 快餐店的顾客分布在城市C的N 个建筑中，这N 个建筑通过恰好N 条双向道路连接起来，不存在任何两条道路连接了相同的两个建筑。任意两个建筑之间至少存在一条由双向道路连接而成的路径。小T的快餐店可以开设在任一建筑中，也可以开设在任意一条道路的某个位置上（该位置与道路两端的建筑的距离不一定是整数）。 现给定城市C的地图（道路分布及其长度），请找出最佳的快餐店选址，输出其与最远的顾客之间的距离。
Input
第一行包含一个整数N，表示城市C中的建筑和道路数目。
接下来N行，每行3个整数，Ai，Bi，Li（1≤i≤N；Li>0），表示一条道路连接了建筑Ai与Bi，其长度为Li 。
Output
仅包含一个实数，四舍五入保留恰好一位小数，表示最佳快餐店选址距离最远用户的距离。
注意：你的结果必须恰好有一位小数，小数位数不正确不得分。
Sample Input
1 2 1
1 4 2
1 3 2
2 4 1
Sample Output
2.0
HINT
数据范围
对于 10%的数据，N<=80,Li=1；
对于 30%的数据，N<=600，Li<=100；
对于 60% 的数据，N<=2000，Li<=10^9；
对于 100% 的数据，N<=10^5，Li<=10^9
首先把环求出来，然后枚举删掉环上某条边，再算出现在的直径，然后取个min
我们先求出不经过环的最长链，然后每次都只用做经过环的最长链了
删掉一条边我们得到了一条链，每个点有两个属性，一个是d[i]，表示不走链最长的距离，一个是S[i]，表示从1走环上的边到i的距离
我们要求的是max{S[j]-S[i]+d[i]+d[j]}，所以我们维护max{S[i]+d[i]}和max{d[i]-S[i]}，但是两个点不能是同一个点所以再维护一下次小值和最大值的编号，用线段树
const
maxn=;
inf=;
type
node=record
max:array[..]of double;
id,l,r,lc,rc:longint;
end;
var
first,huan,fa:array[..maxn]of longint;
d:array[..maxn,..]of double;
next,last:array[..maxn*]of longint;
l,len,a:array[..maxn*]of double;
vis:array[..maxn]of boolean;
f:array[..maxn*]of node;
n,tot,cnt,num,root1,root2:longint;
ans,ans1,s:double; function max(x,y:double):double;
begin
if x>y then exit(x);
exit(y);
end; function min(x,y:double):double;
begin
if x<y then exit(x);
exit(y);
end; procedure insert(x,y:longint;z:double);
begin
inc(tot);
last[tot]:=y;
next[tot]:=first[x];
first[x]:=tot;
l[tot]:=z;
end; procedure dfs1(x:longint);
var
i,j:longint;
begin
i:=first[x];
vis[x]:=true;
while i<> do
begin
if cnt> then exit;
if (last[i]<>fa[x]) and vis[last[i]] then
begin
j:=x;
len[last[i]]:=l[i];
while j<>fa[last[i]] do
begin
inc(cnt);
huan[cnt]:=j;
j:=fa[j];
end;
end;
if not vis[last[i]] then
begin
fa[last[i]]:=x;
len[last[i]]:=l[i];
dfs1(last[i]);
end;
i:=next[i];
end;
end; procedure dfs2(x:longint);
var
i:longint;
begin
vis[x]:=true;
i:=first[x];
while i<> do
begin
if not vis[last[i]] then
begin
dfs2(last[i]);
if d[last[i],]+l[i]>d[x,] then
begin
d[x,]:=d[x,];
d[x,]:=d[last[i],]+l[i];
end
else
if d[last[i],]+l[i]>d[x,] then d[x,]:=d[last[i],]+l[i];
end;
i:=next[i];
end;
if ans<d[x,]+d[x,] then ans:=d[x,]+d[x,];
end; procedure new(x:longint);
begin
f[x].max:=f[f[x].lc].max;
f[x].id:=f[f[x].lc].id;
if f[f[x].rc].max[]>f[x].max[] then
begin
f[x].max[]:=f[x].max[];
f[x].max[]:=f[f[x].rc].max[];
f[x].id:=f[f[x].rc].id;
end
else
if f[f[x].rc].max[]>f[x].max[] then f[x].max[]:=f[f[x].rc].max[];
if f[f[x].rc].max[]>f[x].max[] then f[x].max[]:=f[f[x].rc].max[];
end; procedure build(l,r:longint);
var
now,mid:longint;
begin
inc(num);now:=num;
f[now].l:=l;f[now].r:=r;
if l=r then
begin
f[now].max[]:=a[l];
f[now].max[]:=-inf;
f[now].id:=l;
exit;
end;
mid:=(l+r)>>;
f[now].lc:=num+;build(l,mid);
f[now].rc:=num+;build(mid+,r);
new(now);
end; procedure add(now,x:longint;y:double);
var
mid:longint;
begin
if f[now].l=f[now].r then
begin
f[now].max[]:=y;
exit;
end;
mid:=(f[now].l+f[now].r)>>;
if x<=mid then
add(f[now].lc,x,y)
else
add(f[now].rc,x,y);
new(now);
end; procedure main;
var
i,x,y:longint;
z:double;
begin
read(n);
for i:= to n do
begin
read(x,y,z);
insert(x,y,z);
insert(y,x,z);
end;
dfs1();
for i:= to n do vis[i]:=false;
for i:= to cnt do vis[huan[i]]:=true;
for i:= to cnt do dfs2(huan[i]);
z:=;
for i:= to cnt do
begin
a[i]:=z+d[huan[i],];
z:=z+len[huan[i]];
end;
root1:=num+;build(,cnt);
z:=;
for i:= to cnt do
begin
a[i]:=d[huan[i],]-z;
z:=z+len[huan[i]];
end;
root2:=num+;build(,cnt);
ans1:=inf;
for i:= to cnt do
begin
if f[root1].id<>f[root2].id then
ans1:=min(ans1,f[root1].max[]+f[root2].max[])
else
ans1:=min(ans1,max(f[root1].max[]+f[root2].max[],f[root1].max[]+f[root2].max[]));
s:=s+len[huan[i]];
add(root1,i,z-len[huan[i]]+d[huan[i],]+s);
add(root2,i,d[huan[i],]-z+len[huan[i]]-s);
end;
ans:=max(ans,ans1);
writeln(ans/::);
end; begin
main;
end.