考虑到加上边权为 $0$ 的边没有意义，所以问题转化为从树中找出 $K$ 条不相交的链。

考虑树形动态规划。记 $dp_{u,i,j}$（$0\leq j\leq 2$）表示在以 $u$ 为根的子树中，找出 $j$ 条互不相交的链，且与 $u$ 相连的链上的边的数量为 $j$（即 $u$ 不在链上、在链的一端或者在链的中间）时的最大边权和。转移略。

时间复杂度 $\Theta(nk^2)$。

考虑 WQS 二分，把链的数量加入权值中去，二分链的权值，就可以忽略状态中链的数量这一维，若链太少或太多再进行调整。

时间复杂度 $\Theta(n\log n\log v)$。

/**
 * @date: 2024.01.29
 * @problem: P4383
 * @tags: WQS 二分
 */

#include<bits/stdc++.h>
using namespace std;

int n,k;

struct Edge{
    int to,nxt,w;
}edge[600001];
int cntEdge,head[300001];
inline void addEdge(int u,int v,int w){
    edge[++cntEdge]={v,head[u],w},head[u]=cntEdge;
}

int fa[300001];
void init(int id,int father){
    fa[id]=father;
    for(int i=head[id];i;i=edge[i].nxt){
        int v=edge[i].to;
        if(v==father)continue;
        init(v,id);
    }
}

struct Status{
    long long sum;
    int total;
    inline bool operator<(const Status &x){
        if(sum==x.sum)return total>x.total;
        else return sum<x.sum;
    }
    inline Status operator+(const Status &x){
        return{sum+x.sum,total+x.total};
    }
    inline Status operator+(const int x){
        return{sum+x,total};
    }
}dp[300001][3];

inline void updateStatus(Status &x,Status y){
    if(x<y)x=y;
}

void dfs(int id,long long mid){
    dp[id][0]=dp[id][1]=dp[id][2]={0,0};
    updateStatus(dp[id][2],{-mid,1});
    for(int i=head[id];i;i=edge[i].nxt){
        int v=edge[i].to;
        if(v==fa[id])continue;
        dfs(v,mid);
        updateStatus(dp[id][2],dp[id][2]+dp[v][0]);
        updateStatus(dp[id][2],dp[id][1]+dp[v][1]+edge[i].w+Status{-mid,1});
        updateStatus(dp[id][1],dp[id][1]+dp[v][0]);
        updateStatus(dp[id][1],dp[id][0]+dp[v][1]+edge[i].w);
        updateStatus(dp[id][0],dp[id][0]+dp[v][0]);
    }
    updateStatus(dp[id][0],dp[id][1]+Status{-mid,1});
    updateStatus(dp[id][0],dp[id][2]);
}

int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<n;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        addEdge(u,v,w);
        addEdge(v,u,w);
    }
    init(1,0);
    long long l=-1e12,r=1e12;
    while(l<r){
        long long mid=l+r>>1;
        dfs(1,mid);
        if(dp[1][0].total==k+1){
            printf("%lld\n",dp[1][0].sum+mid*(k+1));
            return 0;
        }
        if(dp[1][0].total>k+1)l=mid+1;
        else r=mid;
    }
    dfs(1,l);
    printf("%lld\n",dp[1][0].sum+l*(k+1));
    return 0;
}