题目描述

给定一棵节点数为 $n$（编号为 $0\sim (n-1)$）的树，每一条边有一个权值。现在要求从点 $0$ 出发，在不经过一个点超过 $k$ 次的情况下经过的边的权值和最大。

每一条边在第一次经过之后权值即变为 $0$；从点 $0$ 出发时也视作经过了 $1$ 次点 $0$；最后不需要回到点 $0$。

输入格式

第一行包括两个正整数，节点数 $n$ 和每个点的最大访问次数 $k$。$n,k\le 10^5$。

接下来的 $n-1$ 行，每行有 $3$ 个正整数 $u,v$ 和 $c$，表示在顶点 $u$ 和顶点 $c$ 之间有一条权值为 $c$ 的无向边。$1\le c\le 10^4$。

输出格式

输出一个正整数，表示可以获得的最大权值。

9 3
0 1 1
0 2 1
1 3 2
1 4 2
1 5 2
2 6 3
2 7 3
2 8 3

15

访问各节点的顺序为：$0,1,5,1,3,1,0,2,6,2,7,2,8$。没有点被访问了超过 $3$ 次。

9 5
0 1 1
0 2 1
1 3 2
1 4 2
1 5 2
2 6 3
2 7 3
2 8 3

17

11 6
1 0 7932
2 1 1952
3 2 2227
4 0 9112
5 4 6067
6 0 6786
7 6 3883
8 4 7137
9 1 2796
10 5 6200

54092