记录编号	205495	评测结果	AAAAAAAAAA
题目名称	不平凡的引线	最终得分	100
用户昵称	Derrick_M	是否通过	通过
代码语言	Pascal	运行时间	0.627 s
提交时间	2015-11-05 14:42:31	内存使用	4.10 MiB

program P2095;
type
  roads=record
  toit,next,val:longint;
end;
var
  road:array[1..200010] of roads;
  min1,min2,minn,list,a:array[1..100010] of longint;
  leaf,flag:array[1..100010] of boolean;
  max0,ans,n,m,i,u,v,w,root,cnt:longint;

procedure add(u,v,w:longint);
begin
  inc(cnt);
  road[cnt].toit:=v;
  road[cnt].next:=list[u];
  road[cnt].val:=w;
  list[u]:=cnt;
  inc(a[v]);
end;

procedure dfs(u:longint);
var
  v,w:longint;
begin
  flag[u]:=true;
  if leaf[u] then
  begin
    min1[u]:=0;
    exit;
  end;
  w:=list[u];
  while w<>0 do
  begin
    v:=road[w].toit;
    if not flag[v] then
    begin
      dfs(v);
      if min1[u]>min1[v]+road[w].val then
      begin
        min2[u]:=min1[u];
        min1[u]:=min1[v]+road[w].val;
        minn[u]:=v;
      end
      else
        if min2[u]>min1[v]+road[w].val then
          min2[u]:=min1[v]+road[w].val;
    end;
    w:=road[w].next;
  end;
end;

function getmin(u,v:longint):longint;
begin
  if u<v then exit(u)
         else exit(v);
end;

procedure work(u,v0:longint);
var
  v,w,min,num:longint;
begin
  flag[u]:=true;
  w:=list[u];
  if leaf[u] then
  begin
    if v0>ans then ans:=v0;
    exit;
  end;
  while w<>0 do
  begin
    v:=road[w].toit;
    if not flag[v] then
    begin
      if minn[u]=v then min:=min2[u]
                   else min:=min1[u];
      num:=getmin(min,v0);
      if (num+road[w].val>=min1[v]) and (min1[v]+road[w].val>=num)
      and (ans<num+road[w].val+min1[v]) then
      ans:=num+road[w].val+min1[v];
      work(v,num+road[w].val);
    end;
    w:=road[w].next;
  end;
end;

begin
  assign(input,'firelead.in');assign(output,'firelead.out');
  reset(input);rewrite(output);
  readln(m);
  n:=m+1;
  for i:=1 to m do
  begin
    readln(u,v,w);
    add(u,v,w);
    add(v,u,w);
  end;
  if m=1 then
  begin
    writeln(w/2:0:1);
    close(input);close(output);
    halt;
  end;
  fillchar(leaf,sizeof(leaf),false);
  for i:=1 to n do
    if a[i]=1 then leaf[i]:=true
              else root:=i;
  fillchar(min1,sizeof(min1),$6F);
  fillchar(min2,sizeof(min2),$6F);
  fillchar(max0,sizeof(max0),$6F);
  dfs(root);
  fillchar(flag,sizeof(flag),false);
  ans:=0;
  work(root,max0);
  writeln(ans/2:0:1);
  close(input);close(output);
end.