1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
#include <bits/stdc++.h>
using namespace std;

#define FOR(i, n) for (int i = 0; i < int(n); ++i)
#define FO(i, a, b) for (int i = (a); i < int(b); ++i)
#define OF(i, a, b) for (int i = (b)-1; i >= int(a); --i)

#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define MAX(a, b) ((b) < (a) ? (a) : (b))

#define REMIN(a, b) ((a) = min(a, b))
#define REMAX(a, b) ((a) = max(a, b))

#define ALL(c) (c).begin(), (c).end()

#define SQR(x) ((x) * (x))

//

const int N = 200'000 + 9;

struct E {
  int dest;
  int cost;
};

int n;
vector<E> tos[N];

struct R {
  long long scores[4];
};

R dfs(int v, int parent) {
  const int dpDim = min((int)tos[v].size() + 3, 2'500);
  const int dpMid = dpDim / 2;
  long long dp[dpDim][2][2];

  int curr = 0;

  FOR(i, dpDim) FOR(j, 2) FOR(k, 2) dp[i][j][k] = -LLONG_MAX / 2;
  dp[dpMid + 0][0][curr] = 0;

  for (auto &[dest, cost] : tos[v]) {
    if (dest == parent)
      continue;

    auto r = dfs(dest, v);

    R sub;
    sub.scores[0] = max(r.scores[1] + cost, r.scores[0]);
    sub.scores[1] = r.scores[2] + cost;
    sub.scores[2] = r.scores[3] + cost;
    sub.scores[3] = r.scores[0] + cost;

    curr = !curr;

    FOR(i, dpDim) FOR(j, 2) {
      dp[i][j][curr] = -LLONG_MAX/2;
      
      if(sub.scores[0] > -LLONG_MAX/4) REMAX(dp[i][j][curr], dp[i][j][!curr] + sub.scores[0]);

      if (i + 1 < dpDim && sub.scores[1] > -LLONG_MAX/4)
        REMAX(dp[i][j][curr], dp[i + 1][j][!curr] + sub.scores[1]);
      if (i - 1 >= 0 && sub.scores[3] > -LLONG_MAX/4)
        REMAX(dp[i][j][curr], dp[i - 1][j][!curr] + sub.scores[3]);

      if(sub.scores[2] > -LLONG_MAX/4) REMAX(dp[i][j][curr], dp[i][!j][!curr] + sub.scores[2]);
    }
  }

  R res;
  res.scores[0] = dp[dpMid][0][curr];
  res.scores[1] = dp[dpMid - 1][0][curr];
  res.scores[2] = dp[dpMid][1][curr];
  res.scores[3] = dp[dpMid + 1][0][curr];

  // cerr << endl << "RESULT " << v << " " << res.scores[0] << " " << res.scores[1] << " " << res.scores[2] << " " << res.scores[3] << endl;

  return res;
}

int main() {
  ios_base::sync_with_stdio(0);

  cin >> n;
  // n = 200'000;

  FOR(i, n - 1) {
    int a, b, c;
    cin >> a >> b >> c;
    // a = i+2;
    // b = 1;
    // c = rand()%(int)2e9 - 1e9;

    --a;
    --b;

    tos[a].push_back({b, c});
    tos[b].push_back({a, c});
  }

  FOR(i,n) shuffle(ALL(tos[i]), default_random_engine(696969));

  auto r = dfs(0, -1);

  cout << r.scores[0] << endl;

  return 0;
}