#include<stdio.h>
#include<ctype.h>
#include<vector>
#include<random>
#include<time.h>
// #include<assert.h>
namespace IO {
	constexpr int bufsize = 230005;
	char buf[bufsize], *f1, *f2;
	#define gtchar() (f1 == f2 && (f2 = buf + fread(f1 = buf, 1, bufsize, stdin)) == buf? EOF: *f1++)
	template<typename t> void read(t &ret)
	{
		int f = ret = 0;
		char ch = gtchar();
		while(!isdigit(ch)) f = ch == '-', ch = gtchar();
		while(isdigit(ch)) ret = (ret << 3) + (ret << 1) + (ch ^ 48), ch = gtchar();
		if(f) ret = -ret;
	}
	#undef gtchar
	template<typename t, typename ...T> void read(t &a, T &...b) {read(a), read(b...);}
}using IO::read;
typedef long long ll;
typedef std::pair<int, int> pii;
constexpr int maxn = 100005;
std::mt19937 rnd(std::random_device{}() ^ time(0));
int n, k, rt[maxn];
std::vector<pii> g[maxn];
struct treap {
	struct node {
		int l, r, size;
		ll val, tag/*整体加*/, tag2/*等差数列加（+0,+d,+2d,...）*/;
		unsigned int p;
	}s[maxn];
	int tot;
	#define l(k) s[k].l
	#define r(k) s[k].r
	#define p(k) s[k].p
	#define v(k) s[k].val
	#define t(k) s[k].tag
	#define t2(k) s[k].tag2
	#define s(k) s[k].size
	void newnode(int k, ll value) {s[k] = {0, 0, 1, value, 0, 0, rnd()};}
	void add(int k, ll delta) {if(k) v(k) += delta, t(k) += delta;}
	void addtag(int k, ll delta) {if(k) v(k) += delta * s(l(k)), t2(k) += delta;}
	void pushdown(int k)
	{
		// assert(k);
		if(t(k)) add(l(k), t(k)), add(r(k), t(k)), t(k) = 0;
		if(t2(k)) addtag(l(k), t2(k)), add(r(k), (s(l(k)) + 1) * t2(k)), addtag(r(k), t2(k)), t2(k) = 0;
	}
	void pushup(int k) {s(k) = s(l(k)) + s(r(k)) + 1;}
	int merge(int l, int r)
	{
		if(!l || !r) return l | r;
		int ret;
		if(p(l) < p(r)) pushdown(ret = l), r(l) = merge(r(l), r);
		else pushdown(ret = r), l(r) = merge(l, l(r));
		pushup(ret);
		return ret;
	}
	void split_size(int k, int rank, int &l, int &r)
	{
		if(!k) return void(l = r = 0);
		int tmp = s(l(k)) + 1;
		pushdown(k);
		if(tmp <= rank) l = k, split_size(r(k), rank - tmp, r(l), r);
		else r = k, split_size(l(k), rank, l, l(r));
		pushup(k);
	}
	void split_value(int k, ll value, int &l, int &r)
	{
		if(!k) return void(l = r = 0);
		pushdown(k);
		if(v(k) >= value) l = k, split_value(r(k), value, r(l), r);
		else r = k, split_value(l(k), value, l, l(r));
		pushup(k);
	}
	void insert(int &k, int idx)
	{
		int l, r;
		split_value(k, v(idx), l, r);
		k = merge(merge(l, idx), r);
	}
	void flip(int k, std::vector<int> &ret)
	{
		if(!k) return;
		pushdown(k);
		flip(l(k), ret);
		ret.push_back(k);
		flip(r(k), ret);
	}
	#undef l
	#undef r
	#undef p
	#undef v
	#undef t
	#undef t2
	#undef s
}tree;
void swap(int &a, int &b) {a ^= b ^= a ^= b;}
int merge(int a, int b)
{
	if(tree.s[a].size > tree.s[b].size) swap(a, b);
	std::vector<int> tmp;
	tree.flip(a, tmp);
	for(int v : tmp) tree.insert(b, v);
	return b;
}
void dfs(int k, int pre)
{
	int &now = rt[k];
	tree.newnode(now = k, 0);
	for(auto i : g[k]) if(i.first != pre)
	{
		int to = i.first;
		dfs(to, k);
		int trash;
		tree.add(rt[to], (ll) i.second * (::k - 1));
		tree.addtag(rt[to], -2 * i.second);
		now = merge(now, rt[to]);
		if(tree.s[now].size > ::k) tree.split_size(now, ::k, now, trash);
	}
	// std::vector<ll> tmp;
	// tree.flip(now, tmp);
	// ll tot = 0;
	// int cnt = 0;
	// printf("point %d:\n", k);
	// for(ll i : tmp) printf("%d:%d\n", ++cnt, tot += i);
}
int main()
{
	// freopen(".in", "r", stdin);
	// freopen(".out", "w", stdout);
	read(n, k);
	for(int i = 1, u, v, w; i < n; i++) read(u, v, w),
		g[u].push_back({v, w}), g[v].push_back({u, w});
	dfs(1, -1);
	std::vector<int> tmp;
	tree.flip(rt[1], tmp);
	ll ans = 0;
	for(int i : tmp) ans += tree.s[i].val;
	printf("%lld\n", ans);
	return 0;
}