#include <bits/stdc++.h>
#pragma GCC optimize(2, 3, "Ofast")
#pragma GCC target( \
    "sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
const double pi = 3.141592653589793238462643383279;
namespace MyMinMax {
template <typename T>
inline T mn(const T x, const T y) {
  return x < y ? x : y;
}
template <typename T>
inline T mx(const T x, const T y) {
  return x > y ? x : y;
}
template <typename T>
inline bool chmin(T &x, const T y) {
  return (x > y) && ((x = y), 1);
}
template <typename T>
inline bool chmax(T &x, const T y) {
  return (x < y) && ((x = y), 1);
}
template <typename T, typename... Args>
inline T mx(const T x, const Args... args) {
  return mx(x, mx(args...));
}
template <typename T, typename... Args>
inline T mn(const T x, const Args... args) {
  return mn(x, mn(args...));
}
}  // namespace MyMinMax
using namespace MyMinMax;
namespace IO {
const int DPAIRSIZ = 1 << 18;
char BB[DPAIRSIZ], *SS = BB, *TT = BB;
inline char getcha() {
  return SS == TT && (TT = (SS = BB) + fread(BB, 1, DPAIRSIZ, stdin), SS == TT)
             ? EOF
             : *SS++;
}
template <typename T = int>
inline T read() {
  T x = 0;
  int fu = 1;
  char c = getcha();
  while (c > 57 || c < 48) {
    if (c == 45) fu = -1;
    c = getcha();
  }
  while (c <= 57 && c >= 48) {
    x = x * 10 + c - 48;
    c = getcha();
  }
  x *= fu;
  return x;
}
template <typename T>
inline void read(T &x) {
  x = 0;
  int fu = 1;
  char c = getcha();
  while (c > 57 || c < 48) {
    if (c == 45) fu = -1;
    c = getcha();
  }
  while (c <= 57 && c >= 48) {
    x = x * 10 + c - 48;
    c = getcha();
  }
  x *= fu;
}
template <typename T>
inline void read(T *bg, T *ed) {
  while (bg != ed) read(*bg++);
}
inline void read(char &ch) {
  ch = getcha();
  while (ch <= 32) ch = getcha();
}
inline void read(char *s) {
  char ch = getcha();
  while (ch <= 32) ch = getcha();
  while (ch > 32) *s++ = ch, ch = getcha();
  *s = '\0';
}
inline void sread(char *s) {
  char ch = getcha();
  while (ch < 32) ch = getcha();
  while (ch >= 32) *s++ = ch, ch = getcha();
  *s = '\0';
}
inline void pread(char *&s) {
  char ch = getcha();
  while (ch <= 32) ch = getcha();
  while (ch > 32) *s++ = ch, ch = getcha();
  *s = '\0';
}
inline void spread(char *&s) {
  char ch = getcha();
  while (ch < 32) ch = getcha();
  while (ch >= 32) *s++ = ch, ch = getcha();
  *s = '\0';
}
template <typename T, typename... Args>
inline void read(T &x, Args &...args) {
  read(x);
  read(args...);
}
char out[DPAIRSIZ], *Out = out;
inline void putcha(char x) {
  *Out++ = x;
  if (Out - out >= (DPAIRSIZ)) fwrite(out, 1, Out - out, stdout), Out = out;
}
template <typename T>
inline void fprint(T x) {
  if (x < 0) putcha(45), x = -x;
  if (x > 9) fprint(x / 10);
  putcha(x % 10 + 48);
}
inline void print() { putcha(10); }
template <typename T>
inline void print(T x) {
  fprint(x);
  putcha(10);
}
inline void print(char *ch) {
  while (*ch != '\0') putcha(*(ch++));
  putcha(10);
}
inline void put(char *ch) {
  while (*ch != '\0') putcha(*(ch++));
}
inline void print(const char *ch) {
  while (*ch != '\0') putcha(*(ch++));
  putcha(10);
}
inline void put(const char *ch) {
  while (*ch != '\0') putcha(*(ch++));
}
template <typename T, typename... Args>
inline void print(T x, Args... args) {
  fprint(x);
  putcha(32);
  print(args...);
}
template <typename... Args>
inline void print(const char *ch, Args... args) {
  while (*ch != '\0') putcha(*(ch++));
  putcha(32);
  print(args...);
}
template <typename... Args>
inline void print(char *ch, Args... args) {
  while (*ch != '\0') putcha(*(ch++));
  putcha(32);
  print(args...);
}
template <typename T, typename... Args>
inline void printl(T x, Args... args) {
  fprint(x);
  putcha(10);
  printl(args...);
}
template <typename... Args>
inline void printl(const char *ch, Args... args) {
  while (*ch != '\0') putcha(*(ch++));
  putcha(10);
  printl(args...);
}
template <typename... Args>
inline void printl(char *ch, Args... args) {
  while (*ch != '\0') putcha(*(ch++));
  putcha(10);
  printl(args...);
}
template <typename T>
inline void sprint(T x) {
  fprint(x);
  putcha(32);
}
template <typename T, typename... Args>
inline void sprint(T x, Args... args) {
  fprint(x);
  putcha(32);
  sprint(args...);
}
template <typename T>
inline void sprint(T *bg, T *ed) {
  while (bg != ed) sprint(*bg++);
}
template <typename T>
inline void print(T *bg, T *ed) {
  while (bg != ed) sprint(*bg++);
  putcha(10);
}
template <typename T>
inline void printl(T *bg, T *ed) {
  while (bg != ed) print(*bg++);
}
class AutoFlush {
 public:
  ~AutoFlush() { fwrite(out, 1, Out - out, stdout); }
} __AutoFlush;
}  // namespace IO
using namespace IO;
const int INF = 0x3f3f3f3f;
const long long INFll = 0x3f3f3f3f3f3f3f3fll;
int n;
const int MAXN = 5005;
int head[MAXN], e[MAXN << 1], cnt, nxt[MAXN << 1];
long long val[MAXN << 1];
inline void add(int u, int v, long long w) {
  nxt[++cnt] = head[u];
  head[u] = cnt;
  e[cnt] = v;
  val[cnt] = w;
}
inline void link(int u, int v, long long w) {
  add(u, v, w);
  add(v, u, w);
}
struct NODE {
  int u, v;
} a[MAXN];
long long dep[MAXN], dis[MAXN], sz[MAXN];
void dfs1(int x, int pre, long long &ans) {
  sz[x] = 1;
  ans += dep[x];
  for (int i = head[x]; i; i = nxt[i]) {
    if (e[i] == pre) continue;
    dep[e[i]] = dep[x] + val[i];
    dfs1(e[i], x, ans);
    sz[x] += sz[e[i]];
  }
}
void dfs2(int x, int pre, long long &ans, const int S) {
  chmin(ans, dis[x]);
  for (int i = head[x]; i; i = nxt[i]) {
    if (e[i] == pre) continue;
    dis[e[i]] = dis[x] + val[i] * (S - (sz[e[i]] << 1));
    dfs2(e[i], x, ans, S);
  }
}
void dfs(int x, int pre, long long &ans, const int ROOT) {
  ans += dep[x] * (x < ROOT);
  for (int i = head[x]; i; i = nxt[i]) {
    if (e[i] == pre) continue;
    dep[e[i]] = dep[x] + val[i];
    dfs(e[i], x, ans, ROOT);
  }
}
long long solve(int x, int pre) {
  dep[x] = dis[x] = 0;
  dfs1(x, pre, dis[x]);
  long long res = dis[x];
  dfs2(x, pre, res, sz[x]);
  return res;
}
signed main() {
  read(n);
  for (int i = (1); i < (n); ++i) {
    read(a[i].u, a[i].v);
    link(a[i].u, a[i].v, read<long long>());
  }
  long long ans = 0;
  for (int i = (1); i <= (n); ++i) {
    dep[i] = 0;
    dfs(i, 0, ans, i);
  }
  const long long base = ans;
  for (int i = (1); i < (n); ++i) {
    const int u = a[i].u, v = a[i].v;
    const long long d1 = solve(u, v), d2 = solve(v, u);
    chmin(ans,
          base - dis[u] * sz[v] - dis[v] * sz[u] + d1 * sz[v] + d2 * sz[u]);
  }
  print(ans);
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

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>
#pragma GCC optimize(2, 3, "Ofast")
#pragma GCC target( \
    "sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
const double pi = 3.141592653589793238462643383279;
namespace MyMinMax {
template <typename T>
inline T mn(const T x, const T y) {
  return x < y ? x : y;
}
template <typename T>
inline T mx(const T x, const T y) {
  return x > y ? x : y;
}
template <typename T>
inline bool chmin(T &x, const T y) {
  return (x > y) && ((x = y), 1);
}
template <typename T>
inline bool chmax(T &x, const T y) {
  return (x < y) && ((x = y), 1);
}
template <typename T, typename... Args>
inline T mx(const T x, const Args... args) {
  return mx(x, mx(args...));
}
template <typename T, typename... Args>
inline T mn(const T x, const Args... args) {
  return mn(x, mn(args...));
}
}  // namespace MyMinMax
using namespace MyMinMax;
namespace IO {
const int DPAIRSIZ = 1 << 18;
char BB[DPAIRSIZ], *SS = BB, *TT = BB;
inline char getcha() {
  return SS == TT && (TT = (SS = BB) + fread(BB, 1, DPAIRSIZ, stdin), SS == TT)
             ? EOF
             : *SS++;
}
template <typename T = int>
inline T read() {
  T x = 0;
  int fu = 1;
  char c = getcha();
  while (c > 57 || c < 48) {
    if (c == 45) fu = -1;
    c = getcha();
  }
  while (c <= 57 && c >= 48) {
    x = x * 10 + c - 48;
    c = getcha();
  }
  x *= fu;
  return x;
}
template <typename T>
inline void read(T &x) {
  x = 0;
  int fu = 1;
  char c = getcha();
  while (c > 57 || c < 48) {
    if (c == 45) fu = -1;
    c = getcha();
  }
  while (c <= 57 && c >= 48) {
    x = x * 10 + c - 48;
    c = getcha();
  }
  x *= fu;
}
template <typename T>
inline void read(T *bg, T *ed) {
  while (bg != ed) read(*bg++);
}
inline void read(char &ch) {
  ch = getcha();
  while (ch <= 32) ch = getcha();
}
inline void read(char *s) {
  char ch = getcha();
  while (ch <= 32) ch = getcha();
  while (ch > 32) *s++ = ch, ch = getcha();
  *s = '\0';
}
inline void sread(char *s) {
  char ch = getcha();
  while (ch < 32) ch = getcha();
  while (ch >= 32) *s++ = ch, ch = getcha();
  *s = '\0';
}
inline void pread(char *&s) {
  char ch = getcha();
  while (ch <= 32) ch = getcha();
  while (ch > 32) *s++ = ch, ch = getcha();
  *s = '\0';
}
inline void spread(char *&s) {
  char ch = getcha();
  while (ch < 32) ch = getcha();
  while (ch >= 32) *s++ = ch, ch = getcha();
  *s = '\0';
}
template <typename T, typename... Args>
inline void read(T &x, Args &...args) {
  read(x);
  read(args...);
}
char out[DPAIRSIZ], *Out = out;
inline void putcha(char x) {
  *Out++ = x;
  if (Out - out >= (DPAIRSIZ)) fwrite(out, 1, Out - out, stdout), Out = out;
}
template <typename T>
inline void fprint(T x) {
  if (x < 0) putcha(45), x = -x;
  if (x > 9) fprint(x / 10);
  putcha(x % 10 + 48);
}
inline void print() { putcha(10); }
template <typename T>
inline void print(T x) {
  fprint(x);
  putcha(10);
}
inline void print(char *ch) {
  while (*ch != '\0') putcha(*(ch++));
  putcha(10);
}
inline void put(char *ch) {
  while (*ch != '\0') putcha(*(ch++));
}
inline void print(const char *ch) {
  while (*ch != '\0') putcha(*(ch++));
  putcha(10);
}
inline void put(const char *ch) {
  while (*ch != '\0') putcha(*(ch++));
}
template <typename T, typename... Args>
inline void print(T x, Args... args) {
  fprint(x);
  putcha(32);
  print(args...);
}
template <typename... Args>
inline void print(const char *ch, Args... args) {
  while (*ch != '\0') putcha(*(ch++));
  putcha(32);
  print(args...);
}
template <typename... Args>
inline void print(char *ch, Args... args) {
  while (*ch != '\0') putcha(*(ch++));
  putcha(32);
  print(args...);
}
template <typename T, typename... Args>
inline void printl(T x, Args... args) {
  fprint(x);
  putcha(10);
  printl(args...);
}
template <typename... Args>
inline void printl(const char *ch, Args... args) {
  while (*ch != '\0') putcha(*(ch++));
  putcha(10);
  printl(args...);
}
template <typename... Args>
inline void printl(char *ch, Args... args) {
  while (*ch != '\0') putcha(*(ch++));
  putcha(10);
  printl(args...);
}
template <typename T>
inline void sprint(T x) {
  fprint(x);
  putcha(32);
}
template <typename T, typename... Args>
inline void sprint(T x, Args... args) {
  fprint(x);
  putcha(32);
  sprint(args...);
}
template <typename T>
inline void sprint(T *bg, T *ed) {
  while (bg != ed) sprint(*bg++);
}
template <typename T>
inline void print(T *bg, T *ed) {
  while (bg != ed) sprint(*bg++);
  putcha(10);
}
template <typename T>
inline void printl(T *bg, T *ed) {
  while (bg != ed) print(*bg++);
}
class AutoFlush {
 public:
  ~AutoFlush() { fwrite(out, 1, Out - out, stdout); }
} __AutoFlush;
}  // namespace IO
using namespace IO;
const int INF = 0x3f3f3f3f;
const long long INFll = 0x3f3f3f3f3f3f3f3fll;
int n;
const int MAXN = 5005;
int head[MAXN], e[MAXN << 1], cnt, nxt[MAXN << 1];
long long val[MAXN << 1];
inline void add(int u, int v, long long w) {
  nxt[++cnt] = head[u];
  head[u] = cnt;
  e[cnt] = v;
  val[cnt] = w;
}
inline void link(int u, int v, long long w) {
  add(u, v, w);
  add(v, u, w);
}
struct NODE {
  int u, v;
} a[MAXN];
long long dep[MAXN], dis[MAXN], sz[MAXN];
void dfs1(int x, int pre, long long &ans) {
  sz[x] = 1;
  ans += dep[x];
  for (int i = head[x]; i; i = nxt[i]) {
    if (e[i] == pre) continue;
    dep[e[i]] = dep[x] + val[i];
    dfs1(e[i], x, ans);
    sz[x] += sz[e[i]];
  }
}
void dfs2(int x, int pre, long long &ans, const int S) {
  chmin(ans, dis[x]);
  for (int i = head[x]; i; i = nxt[i]) {
    if (e[i] == pre) continue;
    dis[e[i]] = dis[x] + val[i] * (S - (sz[e[i]] << 1));
    dfs2(e[i], x, ans, S);
  }
}
void dfs(int x, int pre, long long &ans, const int ROOT) {
  ans += dep[x] * (x < ROOT);
  for (int i = head[x]; i; i = nxt[i]) {
    if (e[i] == pre) continue;
    dep[e[i]] = dep[x] + val[i];
    dfs(e[i], x, ans, ROOT);
  }
}
long long solve(int x, int pre) {
  dep[x] = dis[x] = 0;
  dfs1(x, pre, dis[x]);
  long long res = dis[x];
  dfs2(x, pre, res, sz[x]);
  return res;
}
signed main() {
  read(n);
  for (int i = (1); i < (n); ++i) {
    read(a[i].u, a[i].v);
    link(a[i].u, a[i].v, read<long long>());
  }
  long long ans = 0;
  for (int i = (1); i <= (n); ++i) {
    dep[i] = 0;
    dfs(i, 0, ans, i);
  }
  const long long base = ans;
  for (int i = (1); i < (n); ++i) {
    const int u = a[i].u, v = a[i].v;
    const long long d1 = solve(u, v), d2 = solve(v, u);
    chmin(ans,
          base - dis[u] * sz[v] - dis[v] * sz[u] + d1 * sz[v] + d2 * sz[u]);
  }
  print(ans);
}

```