#include <bits/stdc++.h>
using namespace std;
#define uint unsigned int
#define ll long long
#define eb emplace_back
const int N=1e6+5;
mt19937 rand1(0);
int n,m,bin[N];ll ans,z[N];vector<pair<int,int>> e[N];
int cntp,rt[N];struct Point {int sz,ch[2];uint w;ll tg,tg1,vl;}pt[N];
int New(ll vl)
{
    int p=bin[0]?bin[bin[0]--]:++cntp;
    pt[p]=(Point) {1,{0,0},(uint)rand1(),0,0,vl};return p;
}
void mdf(int p,ll vl) {if(!p) return;pt[p].vl+=vl;pt[p].tg+=vl;}
void mdf1(int p,ll vl)
{if(!p) return;pt[p].vl+=vl*pt[pt[p].ch[0]].sz;pt[p].tg1+=vl;}
void pu(int p) {pt[p].sz=pt[pt[p].ch[0]].sz+pt[pt[p].ch[1]].sz+1;}
void pd(int p)
{
    mdf(pt[p].ch[0],pt[p].tg);
    mdf(pt[p].ch[1],pt[p].tg+pt[p].tg1*(pt[pt[p].ch[0]].sz+1));
    mdf1(pt[p].ch[0],pt[p].tg1);mdf(pt[p].ch[1],pt[p].tg1);
    pt[p].tg=pt[p].tg1=0;
}
void split(int p,ll vl,int &pl,int &pr)
{
    if(!p) {pl=pr=0;return;}pd(p);
    if(pt[p].vl>=vl) pl=p,split(pt[p].ch[1],vl,pt[p].ch[1],pr);
    else pr=p,split(pt[p].ch[0],vl,pl,pt[p].ch[0]);pu(p);
}
int merge(int pl,int pr)
{
    if(!pl || !pr) return pl+pr;pd(pl);pd(pr);
    if(pt[pl].w>pt[pr].w)
    {pt[pl].ch[1]=merge(pt[pl].ch[1],pr);pu(pl);return pl;}
    else {pt[pr].ch[0]=merge(pl,pt[pr].ch[0]);pu(pr);return pr;}
}
void ins(int &p,ll vl)
{int p1,p2;split(p,vl,p1,p2);p=merge(merge(p1,New(vl)),p2);}
void get(int p)
{
    if(!p) return;pd(p);bin[++bin[0]]=p;
    get(pt[p].ch[0]);z[++z[0]]=pt[p].vl;get(pt[p].ch[1]);
}
int merge1(int pl,int pr)
{
    if(pt[pl].sz<pt[pr].sz) swap(pl,pr);
    z[0]=0;get(pr);for(int i=1;i<=z[0];++i) ins(pl,z[i]);return pl;
}
void prt(int p)
{
    if(!p) return;pd(p);
    prt(pt[p].ch[0]);printf("%lld ",pt[p].vl);prt(pt[p].ch[1]);
}
void dfs(int u,int f,int w)
{
    for(auto [v,w]:e[u]) if(v!=f) dfs(v,u,w),rt[u]=merge1(rt[u],rt[v]);
    ins(rt[u],0);mdf(rt[u],1ll*(m-1)*w);mdf1(rt[u],-w*2);
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1,u,v,w;i<n;++i)
        scanf("%d %d %d",&u,&v,&w),e[u].eb(v,w),e[v].eb(u,w);
    dfs(1,0,0);z[0]=0;get(rt[1]);
    for(int i=1;i<=m;++i) ans+=z[i];printf("%lld\n",ans);return 0;
}