#include <bits/stdc++.h>
using namespace std;
const long long int MOD = 1000000007;
const long long BIG = 1446803456761533460LL;
const int Big = 336860180;
const long long int INF = LONG_LONG_MAX;
const vector<vector<long long int> > adj4({{0, 1}, {0, -1}, {1, 0}, {-1, 0}});
const vector<vector<long long int> > adj8(
    {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {-1, -1}, {1, -1}, {-1, 1}, {1, 1}});
long long int gcd(long long int a, long long int b) {
  return b == 0 ? a : gcd(b, a % b);
}
bool isprime(long long int n) {
  if (n == 2 || n == 3) return true;
  if (n < 2 || n % 2 == 0 || n % 3 == 0) return false;
  for (long long int i = 6; (i - 1) * (i - 1) <= n; i += 6) {
    if (n % (i - 1) == 0 || n % (i + 1) == 0) {
      return false;
    }
  }
  return true;
}
vector<bool> sprime;
void genPrime(long long int sz) {
  sprime = vector<bool>(sz, true);
  sprime[0] = false;
  sprime[1] = false;
  for (long long int i = (2); i < (sz); ++i) {
    if (sprime[i]) {
      for (long long int j = i * i; j < sz; j += i) {
        sprime[j] = false;
      }
    }
  }
}
long long int powMod(long long int a, long long int b, long long int mod) {
  long long int n = 1;
  long long int p = a;
  while (b > 0) {
    if (b % 2 == 1) {
      n *= p;
      n %= mod;
    }
    p *= p;
    p %= mod;
    b /= 2;
  }
  return n;
}
long long int modularInverse(long long int a, long long int mod) {
  return powMod(a, mod - 2, mod);
}
long long int binarysearch(long long int l, long long int r,
                           bool (*bsfunction)(long long int)) {
  while (r - l > 1) {
    long long int mid = (l + r) / 2;
    bool val = bsfunction(mid);
    if (val) {
      r = mid;
    } else {
      l = mid;
    }
  }
  return l;
}
stringstream sss;
const long long int maxn = 5010;
vector<pair<long long int, long long int> > g[maxn];
long long int es[maxn][3];
long long int sz[maxn];
long long int down[maxn];
long long int up[maxn];
long long int rt;
long long int mns[2];
long long int mnidx;
void dfsdown(long long int x, long long int par) {
  sz[x] = 1;
  for (auto y : g[x]) {
    long long int v = y.first;
    if (v == par) continue;
    dfsdown(v, x);
    sz[x] += sz[v];
    down[x] += down[v] + y.second * sz[v];
  }
}
void dfsup(long long int x, long long int par) {
  mns[mnidx] = min(mns[mnidx], (up[x] + down[x]));
  for (auto y : g[x]) {
    long long int v = y.first;
    if (v == par) continue;
    up[v] = up[x] + (sz[rt] - sz[v]) * y.second + down[x] -
            (down[v] + y.second * sz[v]);
    dfsup(v, x);
  }
}
void MAIN() {
  long long int n;
  cin >> n;
  for (long long int i = 0; i < (n - 1); ++i) {
    long long int a, b, w;
    cin >> a >> b >> w;
    --a, --b;
    g[a].push_back(make_pair(b, w));
    g[b].push_back(make_pair(a, w));
    es[i][0] = a;
    es[i][1] = b;
    es[i][2] = w;
  }
  rt = 0;
  dfsdown(0, 0);
  dfsup(0, 0);
  long long int res = INF;
  for (long long int e = 0; e < (n - 1); ++e) {
    long long int a = es[e][0];
    long long int b = es[e][1];
    long long int w = es[e][2];
    memset(down, 0, sizeof down);
    memset(up, 0, sizeof up);
    memset(sz, 0, sizeof sz);
    mns[0] = mns[1] = INF;
    mnidx = 0;
    rt = a;
    dfsdown(a, b);
    dfsup(a, b);
    mnidx = 1;
    rt = b;
    dfsdown(b, a);
    dfsup(b, a);
    long long int second = 0;
    for (long long int i = 0; i < (n); ++i) {
      second += up[i] + down[i];
    }
    long long int r = second + w * sz[a] * sz[b] * 2 + sz[a] * 2 * mns[1] +
                      sz[b] * 2 * mns[0];
    res = min(res, (r));
  }
  cout << (res / 2) << endl;
}
long long int TESTCASEN = 1;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(10);
  sss << R"(
6
1 3 1
2 3 1
3 4 100
4 5 2
4 6 1
    )";
  for (long long int test = 0; test < (TESTCASEN); ++test) {
    MAIN();
  }
  return 0;
}

### Prompt

Please formulate a CPP solution to the following problem:

The great Shaass is the new king of the Drakht empire. The empire has n cities which are connected by n - 1 bidirectional roads. Each road has an specific length and connects a pair of cities. There's a unique simple path connecting each pair of cities.

His majesty the great Shaass has decided to tear down one of the roads and build another road with the same length between some pair of cities. He should build such road that it's still possible to travel from each city to any other city. He might build the same road again.

You as his advisor should help him to find a way to make the described action. You should find the way that minimize the total sum of pairwise distances between cities after the action. So calculate the minimum sum.

Input

The first line of the input contains an integer n denoting the number of cities in the empire, (2 ≤ n ≤ 5000). The next n - 1 lines each contains three integers ai, bi and wi showing that two cities ai and bi are connected using a road of length wi, (1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ wi ≤ 106).

Output

On the only line of the output print the minimum pairwise sum of distances between the cities.

Please do not use the %lld specificator to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specificator.

Examples

Input

3
1 2 2
1 3 4


Output

12


Input

6
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1


Output

29


Input

6
1 3 1
2 3 1
3 4 100
4 5 2
4 6 1


Output

825

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const long long int MOD = 1000000007;
const long long BIG = 1446803456761533460LL;
const int Big = 336860180;
const long long int INF = LONG_LONG_MAX;
const vector<vector<long long int> > adj4({{0, 1}, {0, -1}, {1, 0}, {-1, 0}});
const vector<vector<long long int> > adj8(
    {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {-1, -1}, {1, -1}, {-1, 1}, {1, 1}});
long long int gcd(long long int a, long long int b) {
  return b == 0 ? a : gcd(b, a % b);
}
bool isprime(long long int n) {
  if (n == 2 || n == 3) return true;
  if (n < 2 || n % 2 == 0 || n % 3 == 0) return false;
  for (long long int i = 6; (i - 1) * (i - 1) <= n; i += 6) {
    if (n % (i - 1) == 0 || n % (i + 1) == 0) {
      return false;
    }
  }
  return true;
}
vector<bool> sprime;
void genPrime(long long int sz) {
  sprime = vector<bool>(sz, true);
  sprime[0] = false;
  sprime[1] = false;
  for (long long int i = (2); i < (sz); ++i) {
    if (sprime[i]) {
      for (long long int j = i * i; j < sz; j += i) {
        sprime[j] = false;
      }
    }
  }
}
long long int powMod(long long int a, long long int b, long long int mod) {
  long long int n = 1;
  long long int p = a;
  while (b > 0) {
    if (b % 2 == 1) {
      n *= p;
      n %= mod;
    }
    p *= p;
    p %= mod;
    b /= 2;
  }
  return n;
}
long long int modularInverse(long long int a, long long int mod) {
  return powMod(a, mod - 2, mod);
}
long long int binarysearch(long long int l, long long int r,
                           bool (*bsfunction)(long long int)) {
  while (r - l > 1) {
    long long int mid = (l + r) / 2;
    bool val = bsfunction(mid);
    if (val) {
      r = mid;
    } else {
      l = mid;
    }
  }
  return l;
}
stringstream sss;
const long long int maxn = 5010;
vector<pair<long long int, long long int> > g[maxn];
long long int es[maxn][3];
long long int sz[maxn];
long long int down[maxn];
long long int up[maxn];
long long int rt;
long long int mns[2];
long long int mnidx;
void dfsdown(long long int x, long long int par) {
  sz[x] = 1;
  for (auto y : g[x]) {
    long long int v = y.first;
    if (v == par) continue;
    dfsdown(v, x);
    sz[x] += sz[v];
    down[x] += down[v] + y.second * sz[v];
  }
}
void dfsup(long long int x, long long int par) {
  mns[mnidx] = min(mns[mnidx], (up[x] + down[x]));
  for (auto y : g[x]) {
    long long int v = y.first;
    if (v == par) continue;
    up[v] = up[x] + (sz[rt] - sz[v]) * y.second + down[x] -
            (down[v] + y.second * sz[v]);
    dfsup(v, x);
  }
}
void MAIN() {
  long long int n;
  cin >> n;
  for (long long int i = 0; i < (n - 1); ++i) {
    long long int a, b, w;
    cin >> a >> b >> w;
    --a, --b;
    g[a].push_back(make_pair(b, w));
    g[b].push_back(make_pair(a, w));
    es[i][0] = a;
    es[i][1] = b;
    es[i][2] = w;
  }
  rt = 0;
  dfsdown(0, 0);
  dfsup(0, 0);
  long long int res = INF;
  for (long long int e = 0; e < (n - 1); ++e) {
    long long int a = es[e][0];
    long long int b = es[e][1];
    long long int w = es[e][2];
    memset(down, 0, sizeof down);
    memset(up, 0, sizeof up);
    memset(sz, 0, sizeof sz);
    mns[0] = mns[1] = INF;
    mnidx = 0;
    rt = a;
    dfsdown(a, b);
    dfsup(a, b);
    mnidx = 1;
    rt = b;
    dfsdown(b, a);
    dfsup(b, a);
    long long int second = 0;
    for (long long int i = 0; i < (n); ++i) {
      second += up[i] + down[i];
    }
    long long int r = second + w * sz[a] * sz[b] * 2 + sz[a] * 2 * mns[1] +
                      sz[b] * 2 * mns[0];
    res = min(res, (r));
  }
  cout << (res / 2) << endl;
}
long long int TESTCASEN = 1;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(10);
  sss << R"(
6
1 3 1
2 3 1
3 4 100
4 5 2
4 6 1
    )";
  for (long long int test = 0; test < (TESTCASEN); ++test) {
    MAIN();
  }
  return 0;
}

```