题目描述

《胡闹搬家》是一款以搬运为主题的动作解谜游戏。玩家将扮演一名初出茅庐的家具规划及搬运师傅，在繁忙的 Packmore 小镇承接各式各样的搬家任务，完成不同的搬运工作，向成为搬家达人而努力。

现在，搬运者们承接到了新的搬家任务。这个任务要求搬运者们搬运共有 $n$ 件家具，第 $i$ 件家具重量为整数 $x_i$，所有家具必须被全部搬完。每件家具只能由两名指定的搬运者一起出力完成，分别是 $a_i, b_i$。只有当这两人的出力之和大于等于家具重量 $x_i$ 时，这件家具才能被顺利抬走。

搬家结束后，定义搬运者花费的力气为此搬运者的出力总和。你需要计算：在最优的出力分配方案下，所有搬运者花费的力气最大值 最少是多少？

输入格式

第一行包含两个整数 $n, m$（$2 \le n,m \le 200$）。

接下来 $n$ 行，每行三个整数：

• $x_i$（$1 \le x_i \le 10^9$），表示第 $i$ 件家具的重量；
• $a_i, b_i$（$1 \le a_i,b_i \le m$，且 $a_i \ne b_i$），表示必须共同搬运该家具的两人编号。

输出格式

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

4 4
8 1 4
8 1 4
10 1 3
5 2 3

9

解释 1

• 搬运者 1 搬运物品 1 时出力 8，搬运物品 2 时出力 0，搬运物品 3 时候出力 1。
• 搬运者 2 搬运物品 4 时出力 6。
• 搬运者 3 搬运物品 3 时出力 9，搬运物品 4 时出力 0。
• 搬运者 4 搬运物品 1 时出力 0，搬运物品 2 时出力 8。

1. 物品 1 受力之和：8 + 0 ≥ 8，满足条件。
2. 物品 2 受力之和：0 + 8 ≥ 8，满足条件。
3. 物品 3 受力之和：1 + 9 ≥ 10，满足条件。
4. 物品 4 受力之和：6 + 0 ≥ 5，满足条件。

• 搬运者 1 出力之和：8 + 0 + 1 = 9。
• 搬运者 2 出力之和：6。
• 搬运者 3 出力之和：9 + 0 = 9。
• 搬运者 4 出力之和：0 + 8 = 8。

故此方案 所有搬运者花费的力气最大值 最少是 9，可以证明这是最优答案之一。