#include using namespace std; #include using namespace atcoder; using mint=atcoder::modint998244353; #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #define int long long #define rep(i,n) for(int i=0;i<(n);i++) #define rng(i,l,r) for(int i=(l);i<(r);i++) #define rrep(i,n) for(int i=(n)-1;i>=0;i--) #define rrng(i,l,r) for(int i=(r)-1;i>=(l);i--) #define fi first #define se second #define all(x) (x).begin(),(x).end() struct fast_io{fast_io(){cin.tie(nullptr)->sync_with_stdio(false);}}_; template struct RerootingDP { struct edge { int to, idx, xdi; }; RerootingDP(int n_ = 0) : n(n_), inner_edge_id(0) { es.resize(2*n-2); start.resize(2*n-2); if (n == 1) es_build(); } void add_edge(int u, int v, int idx, int xdi){ start[inner_edge_id] = u; es[inner_edge_id] = {v,idx,xdi}; inner_edge_id++; start[inner_edge_id] = v; es[inner_edge_id] = {u,xdi,idx}; inner_edge_id++; if (inner_edge_id == 2*n-2){ es_build(); } } vector build(int root_ = 0){ root = root_; vector subdp(n); subdp[0] = put_vertex(e(),0); outs.resize(n); vector geta(n+1,0); for (int i = 0; i < n; i++) geta[i+1] = start[i+1] - start[i] - 1; geta[root+1]++; for (int i = 0; i < n; i++) geta[i+1] += geta[i]; auto dfs = [&](auto sfs, int v, int f) -> void { E val = e(); for (int i = start[v]; i < start[v+1]; i++){ if (es[i].to == f){ swap(es[start[v+1]-1],es[i]); } if (es[i].to == f) continue; sfs(sfs,es[i].to,v); E nval = put_edge(subdp[es[i].to],es[i].idx); outs[geta[v]++] = nval; val = merge(val,nval); } subdp[v] = put_vertex(val, v); }; dfs(dfs,root,-1); return subdp; } vector reroot(){ vector reverse_edge(n); reverse_edge[root] = e(); vector answers(n); auto dfs = [&](auto sfs, int v) -> void { int le = outs_start(v); int ri = outs_start(v+1); int siz = ri - le; vector rui(siz+1); rui[siz] = e(); for (int i = siz-1; i >= 0; i--){ rui[i] = merge(outs[le+i],rui[i+1]); } answers[v] = put_vertex(merge(rui[0],reverse_edge[v]),v); E lui = e(); for (int i = 0; i < siz; i++){ V rdp = put_vertex(merge(merge(lui,rui[i+1]),reverse_edge[v]),v); reverse_edge[es[start[v]+i].to] = put_edge(rdp,es[start[v]+i].xdi); lui = merge(lui,outs[le+i]); sfs(sfs,es[start[v]+i].to); } }; dfs(dfs,root); return answers; } private: int n, root, inner_edge_id; vector outs; vector es; vector start; int outs_start(int v){ int res = start[v] - v; if (root < v) res++; return res; } void es_build(){ vector nes(2*n-2); vector nstart(n+2,0); for (int i = 0; i < 2*n-2; i++) nstart[start[i]+2]++; for (int i = 0; i < n; i++) nstart[i+1] += nstart[i]; for (int i = 0; i < 2*n-2; i++) nes[nstart[start[i]+1]++] = es[i]; swap(es,nes); swap(start,nstart); } }; int merge(int a,int b){return max(a,b);} int e(){return 0;} int W[200009]; int put_edge(int x,int idx){ return x+W[idx]; } int put_vertex(int x,int idx){ return x; } signed main(){ int N;cin>>N; RerootingDP dp(N); rep(i,N-1){ int u,v,w;cin>>u>>v>>w;u--;v--; dp.add_edge(u,v,i,i); W[i]=w; } dp.build(); auto ret=dp.reroot(); cout<<*max_element(all(ret))<