#2478. 「九省联考 2018」林克卡特树

小 L 最近沉迷于塞尔达传说：荒野之息（The Legend of Zelda: Breath of The Wild）无法自拔，他尤其喜欢游戏中的迷你挑战。

游戏中有一个叫做 “LCT” 的挑战，它的规则是这样子的：现在有一个 个点的树（Tree），每条边有一个整数边权 ，若 ，表示走这条边会获得 的收益；若 ，则表示走这条边需要支付 的过路费。小 L 需要控制主角 Link 切掉（Cut）树上的恰好 条边，然后再连接 条边权为 边，得到一棵新的树。接着，他会选择树上的两个点 ，并沿着树上连接这两点的简单路径从 走到 ，并为经过的每条边支付过路费 / 获取相应收益。

海拉鲁大陆之神 TemporaryDO 想考验一下 Link。他告诉 Link，如果 Link 能切掉合适的边、选择合适的路径从而使总收益-总过路费最大化的话，就把传说中的大师之剑送给他。

小 L 想得到大师之剑，于是他找到了你来帮忙，请你告诉他，Link 能得到的总收益-总过路费最大是多少。

输入第一行包含两个正整数 ，保证 。

接下来 行，每行包含三个整数 ，表示第 条边连接图中的 两点，它的边权为 。

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

样例输入 1

5 1
1 2 3
2 3 5
2 4 -3
4 5 6

样例输出 1

14

样例解释 1

一种可能的最优方案为：切掉 这条边，连接 这条边，选择 。

样例 2

见附加文件中的 lct/lct2.in 与 lct/lct2.ans。

对于 的数据， ;

对于另外 的数据， ;

对于另外 的数据， ;

对于另外 的数据， ;

对于其他数据，没有特殊约定。

对于全部的测试数据，保证有 , , 。

提示：题目并不难。