#include using namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; vector>> Graph(N); for(int i=0; i> u >> v; u--; v--; int w; cin >> w; Graph.at(u).push_back({v,w}); Graph.at(v).push_back({u,w}); } vector stop(N); auto Size = [&](auto Size,int pos,int back) -> int { if(stop.at(pos)) return 0; int ret = 1; for(auto [to,w] : Graph.at(pos)) if(to != back) ret += Size(Size,to,pos); return ret; }; auto centroid = [&](auto centroid,int pos,int back,int siz) -> pair { if(stop.at(pos)) return {0,-1}; int ret = 1; bool cen = true; for(auto [to,w] : Graph.at(pos)){ if(to == back) continue; auto ko = centroid(centroid,to,pos,siz); if(ko.second != -1) return {-1,ko.second}; if(ko.first > siz/2) cen = false; ret += ko.first; } if(siz-ret > siz/2) cen = false; if(cen) return {-1,pos}; else return {ret,-1}; }; long long answer = 0,inf = 1e18;; queue Q; Q.push(0); while(Q.size()){ int pos = Q.front(); Q.pop(); int siz = Size(Size,pos,-1); pos = centroid(centroid,pos,-1,siz).second; auto dfs = [&](auto dfs,int p,int b) -> long long { if(stop.at(p)) return -inf; long long ret = 0; for(auto [to,w] : Graph.at(p)){ if(to == b) continue; ret = max(ret,w+dfs(dfs,to,p)); } return ret; }; int n = Graph.at(pos).size(); pair Maxw = {0,0}; auto upd = [&](pair &a,long long b){ auto &[v1,v2] = a; if(v1 < b) v2 = v1,v1 = b; else if(v2 < b) v2 = b; }; for(int i=0; i