#Z0003. 猫咖
猫咖
题目描述
老板开了两家猫咖店,里面一共有 只猫,每只猫猫的编号为。它们之间的关系并不好,很多猫之间甚至互相仇视,如果某两只猫互相仇视而且还在同一家店里面则一定会打架,并且会损坏店内的装饰,导致亏损一定的金钱 。
店长会把损失金额从大到小列出一张表给老板看,但是老板只会看表的第一条也就是损失金额最大的那一条。损失的太多了老板就会生气,会扣店长的奖金。
店长现在压力倍增,他准备重新分配这些猫猫在这两家不同的店里,让损失金额达到最小。
那么,应如何分配猫猫,才能使老板看到的那个损失的金额最小?这个最小值是多少?
输入格式
每行中两个数之间用一个空格隔开。第一行为两个正整数 ,分别表示猫猫的数目以及存在仇恨的猫猫对数。接下来的 行每行为三个正整数 ,表示 号和 号猫猫之间存在仇恨,其打架亏损的金额为 。数据保证 ,且每对猫猫组合只出现一次。
输出格式
共一行,为店长看到的那张表的最大亏损金额。如果猫猫未发生任何冲突事件,请输出 0。
Samples
4 6
1 4 2534
2 3 3512
1 2 28351
1 3 6618
2 4 1805
3 4 12884
3512
样例解释
将猫猫1,4放在一家店中,2,3放在另一家店中为最优解。
数据范围
对于 的数据有 。
对于 的数据有 。
对于 的数据有 。