[2018多省省队联测]林克卡特树

内存限制：128 MiB 时间限制：1 Sec

小L最近沉迷于塞尔达传说：荒野之息（The Legend of Zelda: Breath of The Wild）无法自拔

他尤其喜欢游戏中的迷你挑战。

游戏中有一个叫做“LCT”的挑战，它的规则是这样子的：现在有一个N个点的树（Tree），每条边有一个整数边权

vi，若vi>=0，表示走这条边会获得vi的收益；若vi<0，则表示走这条边需要支付-vi的过路费。小L需要控制主角L

ink切掉（Cut）树上的恰好K条边，然后再连接K条边权为0的边，得到一棵新的树。接着，他会选择树上的两个点p

;q，并沿着树上连接这两点的简单路径从p走到q，并为经过的每条边支付过路费/获取相应收益。海拉鲁大陆之神T

emporaryDO想考验一下Link。他告诉Link，如果Link能切掉合适的边、选择合适的路径从而使总收益-总过路费最

大化的话，就把传说中的大师之剑送给他。小L想得到大师之剑，于是他找到了你来帮忙，请你告诉他，Link能得

到的总收益-总过路费最大是多少。

输入第一行包含两个正整数N;K，保证0<=K<N<=3*10^5

接下来N-1行，每行包含三个整数xi;yi;vi，表示第i条边连接图中的xi;yi两点，它的边权为vi。

1 <= N <= 3 * 10^5

1 <= xi; yi <= N; |vi| <= 10^6

输出一行一个整数，表示答案。


			14

一种可能的最优方案为：切掉(2,4,-3) 这条边，连接(3,4,0) 这条边，选择(p,q) = (1; 5)

请不要提交！数据如下:https://begin.lydsy.com/JudgeOnline/upload/lct.rar

原题面:www.lydsy.com/JudgeOnline/upload/201804/day2(3).pdf

#5252. [2018多省省队联测]林克卡特树