#include #define rep(i, n) for(int i=0, i##_len=(n); i=0; --i) #define rreps(i, n) for(int i=((int)(n)); i>0; --i) #define all(v) (v).begin(), (v).end() #define el '\n' using namespace std; using ll = long long; using ull = unsigned long long; using vi = vector; using vvi = vector>; using vvvi = vector>>; using vl = vector; using vvl = vector>; using vvvl = vector>>; using vs = vector; using pi = pair; using pl = pair; template using min_priority_queue = priority_queue, greater>; template bool chmax(T &a, const T &b) { if (a bool chmin(T &a, const T &b) { if (b bool chmaxeq(T &a, const T &b) { if (a<=b) { a=b; return 1; } return 0; } template bool chmineq(T &a, const T &b) { if (b<=a) { a=b; return 1; } return 0; } bool yes(bool a=true) { cout << (a?"yes":"no") << el; return a; } bool no(bool a=true) { cout << (a?"no":"yes") << el; return a; } bool Yes(bool a=true) { cout << (a?"Yes":"No") << el; return a; } bool No(bool a=true) { cout << (a?"No":"Yes") << el; return a; } bool YES(bool a=true) { cout << (a?"YES":"NO") << el; return a; } bool NO(bool a=true) { cout << (a?"NO":"YES") << el; return a; } template istream &operator>>(istream &is, pair &p); template ostream &operator<<(ostream &os, const pair &p); template istream &operator>>(istream &is, vector &v); template ostream &operator<<(ostream &os, const vector &v); template istream &operator>>(istream &is, pair &p) { return is >> p.first >> p.second; } template ostream &operator<<(ostream &os, const pair &p) { return os << p.first << ' ' << p.second; } template istream &operator>>(istream &is, vector &v) { int sz = v.size(); for (int i = 0; i < sz; i++) is >> v[i]; return is; } template ostream &operator<<(ostream &os, const vector &v) { int sz = v.size(); for (int i = 0; i < sz; i++) { if (i) os << ' '; os << v[i]; } return os; } void _main(); int main() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(16); _main(); return 0; } template struct rerooting { rerooting(int n) : _graph(n), _lprod(n), _rprod(n) {} int add_edge(int from, int to) { int pos = _graph[from].size(); int rev_pos = _graph[to].size(); int index = _nodes.size(); _graph[from].push_back(node(to, rev_pos, index)); _graph[to].push_back(node(from, pos, index)); _nodes.push_back(node_memo(from, pos)); return index; } vector calc() { _dfs1(); _dfs2(); vector res; for (int i = 0; i < _graph.size(); i++) res.push_back(put_vertex(_lprod[i][_graph[i].size()], i)); return res; } S partial(int index, int s) { int from = _nodes[index].from; int pos = _nodes[index].pos; int to = _graph[from][pos].to; int rev_pos = _graph[from][pos].rev_pos; if (s != _graph[from][pos].to) { swap(from, to); swap(pos, rev_pos); } assert(s == _graph[from][pos].to); return put_vertex(op(_lprod[to][rev_pos], _rprod[to][rev_pos+1]), to); } private: struct node { int to, rev_pos, index; S val; node(int to, int rev_pos, int index) : to(to), rev_pos(rev_pos), index(index), val(e()) {} }; struct node_memo { int from, pos; node_memo(int from, int pos) : from(from), pos(pos) {} }; vector> _graph; vector _nodes; vector> _lprod, _rprod; S _dfs1(int s=0, int p=-1) { int deg = _graph[s].size(); S prod = e(); for (int i = 0; i < deg; i++) { int t = _graph[s][i].to; if (t == p) continue; S partial = put_edge(_dfs1(t, s), _graph[s][i].index); _graph[s][i].val = partial; prod = op(prod, partial); } return put_vertex(prod, s); } void _dfs2(int s=0, int p=-1, S prod_par=e()) { int deg = _graph[s].size(); _lprod[s].resize(deg+1, e()); _rprod[s].resize(deg+1, e()); S prod = e(); for (int i = 0; i < deg; i++) { int t = _graph[s][i].to; if (t == p) _graph[s][i].val = put_edge(prod_par, _graph[s][i].index); prod = op(prod, _graph[s][i].val); _lprod[s][i+1] = prod; } prod = e(); for (int i = deg-1; i >= 0; i--) { prod = op(prod, _graph[s][i].val); _rprod[s][i] = prod; } for (int i = 0; i < deg; i++) { int t = _graph[s][i].to; if (t == p) continue; _dfs2(t, s, put_vertex(op(_lprod[s][i], _rprod[s][i+1]), s)); } } }; vl w; ll op(ll a, ll b) { return max(a, b); } ll e() { return 0; } ll put_vertex(ll x, int i) { return x; } ll put_edge(ll x, int i) { return x+w[i]; } void _main() { ll N; cin >> N; w = vl(N-1); rerooting rr(N); rep(i, N-1) { ll u, v; cin >> u >> v >> w[i]; u--; v--; rr.add_edge(u, v); } ll ans = 0; for (auto &x : rr.calc()) chmax(ans, x); cout << ans << el; }