408966: GYM103389 J 最大权边独立集

给定一张 $$$n$$$ 个点 $$$n-1$$$ 条边的连通无向图，点的编号依次为 $$$1$$$ 到 $$$n$$$，第 $$$i$$$ 条边的边权为 $$$w_i$$$。

请往图中添加恰好 $$$k$$$ 条边权为 $$$p$$$ 的边，使得最大权边独立集的边权和最大，即在新图中找到一系列不含公共端点的边，使得这些边的边权和最大。注意：添加的边必须连接两个不同的点，但是两个点之间允许存在多条边。

第一行包含三个整数 $$$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$$$。

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

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

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

15