正解：不会做。
写一个爬山算法就过官方数据了(逃
具体来说就是每次随机一个根，然后迭代找最长路的那个点。
多随机几次取$max$就行了。正解以后再补。。
#include <bits/stdc++.h>
#define il inline
#define RG register
#define ll long long
#define N (100005) using namespace std; int pos[N],vis[N],q[N],n;
ll dis[][N],ans; il int gi(){
RG int x=,q=; RG char ch=getchar();
while ((ch<'' || ch>'') && ch!='-') ch=getchar();
if (ch=='-') q=-,ch=getchar();
while (ch>='' && ch<='') x=x*+ch-'',ch=getchar();
return q*x;
} struct graph{ struct edge{ int nt,to; ll dis; }g[N<<]; int head[N],num; il void insert(RG int from,RG int to,RG ll dis){
g[++num]=(edge){head[from],to,dis},head[from]=num; return;
} }G[]; il void bfs(RG int op,RG int S){
for (RG int i=;i<=n;++i) vis[i]=;
RG int h=,t=; q[t]=S,vis[S]=,dis[op][S]=;
while (h<t){
RG int x=q[++h],v;
for (RG int i=G[op].head[x];i;i=G[op].g[i].nt){
v=G[op].g[i].to; if (vis[v]) continue;
vis[v]=,q[++t]=v,dis[op][v]=dis[op][x]+G[op].g[i].dis;
}
}
return;
} int main(){
#ifndef ONLINE_JUDGE
freopen("tunnel.in","r",stdin);
freopen("tunnel.out","w",stdout);
#endif
srand(),n=gi();
for (RG int i=,u,v;i<n;++i){
u=gi(),v=gi(); RG ll w; scanf("%lld",&w);
G[].insert(u,v,w),G[].insert(v,u,w);
}
for (RG int i=,u,v;i<n;++i){
u=gi(),v=gi(); RG ll w; scanf("%lld",&w);
G[].insert(u,v,w),G[].insert(v,u,w);
}
for (RG int i=,u,v;i<n;++i){
u=gi(),v=gi(); RG ll w; scanf("%lld",&w);
G[].insert(u,v,w),G[].insert(v,u,w);
}
for (RG int i=;i<=n;++i) pos[i]=i;
random_shuffle(pos+,pos+n+);
for (RG int T=,rt;T<=;++T){
rt=pos[T]; RG ll ret=;
while (){
bfs(,rt),bfs(,rt),bfs(,rt);
RG ll res=; RG int id=;
for (RG int i=;i<=n;++i)
if (res<dis[][i]+dis[][i]+dis[][i])
res=dis[][i]+dis[][i]+dis[][i],id=i;
if (ret<res) ret=res,rt=id; else break;
}
ans=max(ans,ret);
}
cout<<ans; return ;
}