树形DP。由于n只有5000，可以直接枚举边。
枚举边，将树分成两个子树，然后从每个子树中选出一个点分别为u,v，那么答案就是:
子树1中任意两点距离总和+子树2中任意两点距离总和+子树1中任意一点到u的距离和*子树2的节点个数+子树2中任意一点到v的距离和*子树1的节点个数+子树1的节点个数*子树2的节点个数*当前枚举边的权值。
当枚举的边一定时，那么要选取的点就是子树中到所有点的距离总和最小的点。对树进行dfs，同时记录子树的节点个数，所有孩子节点到当前根节点的距离总和，以及当前子树中任意两点距离和。然后在进行dfs求解到该子树中所有点距离和最小的点。
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef pair <int, int> pii;
#define maxn 5005
#define INF 0x3f3f3f3f3f3f3f3fll int f[maxn], h[maxn], w[maxn];
vector<pii> g[maxn];
int son[maxn];
LL d[maxn], s[maxn]; void dfs(int v, int rt){
son[v] = , d[v] = , s[v] = ;
for(int i = ; i != g[v].size(); i ++){
int u = g[v][i].first;
if(u==rt) continue;
dfs(u, v);
s[v] += s[u] + d[u]*son[v] + d[v]*son[u] + (LL)son[u] * son[v] * g[v][i].second;
d[v] += d[u] + (LL)son[u] * g[v][i].second;
son[v] += son[u];
}
son[v] ++;
s[v] += d[v];
}
void dfsw(int v, int rt, LL &minn){
minn = min(d[v], minn);
for(int i = ; i != g[v].size(); i ++){
int u = g[v][i].first;
if(u==rt) continue;
d[u] = d[u] + (d[v] - d[u] - (LL)son[u]*g[v][i].second) + (LL)(son[v] - son[u])*g[v][i].second;
son[u] = son[v];
dfsw(u, v, minn);
}
}
int main(){
//freopen("test.in", "r", stdin);
for(int n; scanf("%d", &n)!=EOF; ){
for(int i = ; i <= n; i ++){
g[i].clear();
}
for(int i = , x, y, z; i < n; i ++){
scanf("%d%d%d", &x, &y, &z);
f[i] = x, h[i] = y, w[i] = z;
g[x].push_back(make_pair(y, z));
g[y].push_back(make_pair(x, z));
}
LL ans = INF, minn = INF, sum = ;
for(int i = ; i < n; i ++){
minn = INF;
dfs(f[i], h[i]);
dfsw(f[i], h[i], minn);
sum = ;
sum = (n - son[f[i]]) * minn + s[f[i]];
minn = INF;
dfs(h[i], f[i]);
dfsw(h[i], f[i], minn);
sum = sum + (n - son[h[i]]) * minn + s[h[i]] + (LL)son[f[i]]*son[h[i]]*w[i];
ans = min(ans, sum);
}
printf("%I64d\n", ans);
}
return ;
}