for(int i=1;i
edge[a].push_back(b);
edge[b].push_back(a);
mp[a][b] = mp[b][a] = c;
in[tot++] = Edge(a,b,c);
}
dfs(1,0);
long long INF = (long long)1000000000*(long long)1000000000;
long long ans = INF;
for(int i=0;i
if(dep[u] > dep[v]) swap(u,v);
node = v;
Mi = INF; sum = 0;
dfs1(1,0,1);
dfs2(1,0,1);
long long tmp = (long long)(son[1]-son[node])*(son[node])*in[i].w;
tmp += Mi * (son[node]) ;
tmp += sum;
Mi = INF; sum = 0;
DFS(node,u);
dfs1(node,u,node);
dfs2(node,u,node);
tmp += Mi * (son[1]-son[node]);
tmp += sum;
if(tmp < ans) ans = tmp;
}
printf("%I64d\n",ans);
return 0;
}