#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
template<class T> void check_min(T &a, const T &b){ a = (a < b) ? a : b; }
template<class T> void check_max(T &a, const T &b){ a = (a > b) ? a : b; }
#define all(x) (x).begin(), (x).end()

void files(string name){
    freopen((name + ".in").c_str(), "r", stdin);
    freopen((name + ".out").c_str(), "w", stdout);
}

const int N = 5000 + 3;
const int K = 500 + 3;
const int INF = 1e7;

int n, k;
vector<pair<int, int>> adj[N];

vector<int> dp[2][N];

void merge(int u, int to, int e){
    int new_sz = min(k + 1, (int)dp[0][u].size() + (int)dp[0][to].size());

    vector<int> tmp[2];
    tmp[0] = dp[0][u];
    tmp[1] = dp[1][u];

    dp[0][u].clear();
    dp[0][u].resize(new_sz, INF);
    dp[1][u].clear();
    dp[1][u].resize(new_sz, INF);

    for(int i = 0; i < dp[0][to].size(); ++i){
        for(int j = 0; j < tmp[0].size(); ++j){
            if(i + j >= new_sz) continue;

            check_min(dp[e][u][i + j], dp[0][to][i] + tmp[e][j]);
            if(i + j + 1 < new_sz)
                check_min(dp[e][u][i + j + 1], dp[1][to][i] + tmp[e][j]);

            check_min(dp[!e][u][i + j], dp[1][to][i] + tmp[!e][j]);
            if(i + j + 1 < new_sz)
                check_min(dp[!e][u][i + j + 1], dp[0][to][i] + tmp[!e][j]);
        }
    }
}

void solve(int u, int p = -1){
    // cout << u << " u" << endl;
    for(auto [to, e]: adj[u]){
        if(to == p) continue;

        solve(to, u);
    }

    dp[0][u] = {1};
    dp[1][u] = {0};

    if(adj[u].size() == (p != -1)){    
        return;
    }

    for(auto [to, e]: adj[u]){
        if(to == p) continue;
        merge(u, to, e);
    }

   /* cout << "x " << u << ":" << endl;
    for(int i = 0; i < 2; ++i){
        cout << i << ": ";
        for(int x: dp[i][u])
            cout << x << " ";
        cout << endl;
    }*/
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    files("xorfun");

    cin >> n >> k;
    for(int i = 0; i < n - 1; ++i){
        int u, v, w;
        cin >> u >> v >> w;
        w = __builtin_popcount(w) & 1;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    solve(1);

    int mn = INF;
    for(int i = 0; i <= min(k, (int)dp[0][1].size() - 1); ++i)
        check_min(mn, min(dp[1][1][i], dp[0][1][i]));
    cout << mn * (n - mn) << "\n";
}