1
2
3
4
5

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

1

17

 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

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn = 2005;
const int INF = 1000000007;
inline int getint() { int r = 0; bool b = true; char c = getchar(); while ('0' > c || c > '9') {if (c == '-') b = false; c = getchar();} while ('0' <= c && c <= '9') {r = (r<<3) + (r<<1) + (c-'0'); c = getchar();} if (b) return r; return -r; }
int siz[maxn], h[maxn], cnte, n, m;
struct edge_t { int to, next; LL w; } edge[maxn<<1];
void ins(int x, int y, LL z) { edge[++cnte].to = y; edge[cnte].next = h[x]; edge[cnte].w = z; h[x] = cnte; }
inline void g(LL &a, const LL &b) { if (a < b) a = b; }
LL dp[maxn][maxn], f_dst[maxn][maxn];
void dfs(int now, int father) {
    LL *f = f_dst[now];
    siz[now] = 1;
    for (int i = h[now]; i; i = edge[i].next) {
        if (edge[i].to == father) continue;
        dfs(edge[i].to, now);
        for (int j = 0; j <= siz[now] + siz[edge[i].to]; ++j) f[j] = -INF;
        for (int j = 0; j <= siz[now]; ++j)
            for (int k = 0; k <= siz[edge[i].to]; ++k)
                g(f[j+k], dp[now][j] + dp[edge[i].to][k] + LL(m-k)*LL(k)*edge[i].w + LL(n-m-(siz[edge[i].to]-k))*LL(siz[edge[i].to]-k)*edge[i].w);
        siz[now] += siz[edge[i].to];
        for (int j = 0; j <= siz[now]; ++j) dp[now][j] = f[j];
    }
}
int main() {
    int x, y; LL z;
    n = getint();
    m = getint();
    for (int i = 1; i < n; ++i) {
        x = getint();
        y = getint();
        z = getint();
        ins(x, y, z);
        ins(y, x, z);
    }
    dfs(1, -1);
    printf("%lld", dp[1][m]);
}