You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

老板开了两家猫咖店，里面一共有 $n$ 只猫，每只猫猫的编号为$1\sim n$。它们之间的关系并不好，很多猫之间甚至互相仇视，如果某两只猫互相仇视而且还在同一家店里面则一定会打架，并且会损坏店内的装饰，导致亏损一定的金钱 $c$。

店长会把损失金额从大到小列出一张表给老板看，但是老板只会看表的第一条也就是损失金额最大的那一条。损失的太多了老板就会生气，会扣店长的奖金。

店长现在压力倍增，他准备重新分配这些猫猫在这两家不同的店里，让损失金额达到最小。

那么，应如何分配猫猫，才能使老板看到的那个损失的金额最小？这个最小值是多少？

输入格式

每行中两个数之间用一个空格隔开。第一行为两个正整数 $n,m$，分别表示猫猫的数目以及存在仇恨的猫猫对数。接下来的 $m$ 行每行为三个正整数 $a_j,b_j,c_j$，表示 $a_j$ 号和 $b_j$ 号猫猫之间存在仇恨，其打架亏损的金额为 $c_j$。数据保证 $1<a_j\leq b_j\leq N, 0 < c_j\leq 10^9$，且每对猫猫组合只出现一次。

输出格式

共一行，为店长看到的那张表的最大亏损金额。如果猫猫未发生任何冲突事件，请输出 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放在另一家店中为最优解。

数据范围

对于 $30\%$ 的数据有 $N\leq 15$。

对于 $70\%$ 的数据有 $N\leq 2000,M\leq 50000$。

对于 $100\%$ 的数据有 $N\leq 20000,M\leq 100000$。