最大权边独立集

Description:

Input:

第一行包含三个整数 $$$n,k,p$$$ ($$$2\leq n\leq 100\,000$$$, $$$0\leq k\leq 100$$$, $$$1\leq p\leq 10^9$$$)，表示点数、要添加的边数以及要添加的边的权值。

接下来 $$$n-1$$$ 行，第$$$i$$$行包含三个正整数 $$$u_i,v_i,w_i$$$ ($$$1\leq u_i,v_i\leq n$$$, $$$1\leq w_i\leq 10^9$$$)，表示第 $$$i$$$ 条边的端点是 $$$u_i$$$ 和 $$$v_i$$$，其边权为 $$$w_i$$$。

输入数据保证图是连通图。

Output:

输出一行一个正整数，即新图的最大权边独立集的边权和。

Sample Input:

4 1 7
1 2 8
2 3 4
2 4 6

Sample Output:

15